堆是一棵完全二叉樹(shù)。堆分為大根堆和小根堆，大根堆是父節(jié)點(diǎn)大于左右子節(jié)點(diǎn)，并且左右子樹(shù)也滿足該性質(zhì)的完全二叉樹(shù)。小根堆相反?？梢岳枚褋?lái)實(shí)現(xiàn)優(yōu)先隊(duì)列。

由于是完全二叉樹(shù)，所以可以使用數(shù)組來(lái)表示堆，索引從0開(kāi)始[0:length-1]。結(jié)點(diǎn)i的左右子節(jié)點(diǎn)分別為2i+1,2i+2。長(zhǎng)度為length的樹(shù)的最后一個(gè)非葉子節(jié)點(diǎn)為length//2-1。當(dāng)前節(jié)點(diǎn)i的父節(jié)點(diǎn)為(i-1)//2。其中//表示向下取整。

以大根堆舉例。當(dāng)每次插入或者刪除的時(shí)候，為了保證堆的結(jié)構(gòu)特征不被破壞，需要進(jìn)行調(diào)整。調(diào)整分為兩種，一種是從上往下，將小的數(shù)下沉。一種是從下往上，令大的數(shù)上浮。

具體實(shí)現(xiàn)如下：

首先編寫(xiě)幾個(gè)魔術(shù)方法。包括構(gòu)造函數(shù)，可以直接調(diào)用len來(lái)返回data數(shù)組長(zhǎng)度的函數(shù)，一個(gè)打印data內(nèi)容的函數(shù)

 def __init__(self, data=[]):
    self.data = data
    self.construct_heap()

 def __len__(self):
    return len(self.data)

 def __str__(self):
    return str(self.data)

定義一個(gè)swap函數(shù)，來(lái)方便的交換數(shù)組中兩個(gè)索引處的值。

  def swap(self, i, j):
    self.data[i], self.data[j] = self.data[j], self.data[i]

定義float_up方法，使堆中大的數(shù)能浮上來(lái)。當(dāng)前節(jié)點(diǎn)不為根節(jié)點(diǎn)，并且當(dāng)前節(jié)點(diǎn)數(shù)據(jù)大小大于父節(jié)點(diǎn)時(shí)，上浮。

 def float_up(self, i):
    while i > 0 and self.data[i] > self.data[(i - 1) // 2]:
      self.swap(i, (i - 1) // 2)
      i = (i - 1) // 2

定義sink_down方法，使堆中小的數(shù)沉下去。當(dāng)前節(jié)點(diǎn)不為葉子節(jié)點(diǎn)時(shí)，如果小于左孩子或右孩子的數(shù)據(jù)，則和左右孩子中較大的換一下位置。

def sink_down(self, i):
    while i < len(self) // 2:
      l, r = 2 * i + 1, 2 * i + 2
      if r < len(self) and self.data[l] < self.data[r]:
        l = r
      if self.data[i] < self.data[l]:
        self.swap(i, l)

      i = l

實(shí)現(xiàn)append方法，能夠動(dòng)態(tài)地添加數(shù)據(jù)。在數(shù)據(jù)數(shù)組尾部添加數(shù)據(jù)，然后將數(shù)據(jù)上浮。

  def append(self, data):
    self.data.append(data)
    self.float_up(len(self) - 1)

實(shí)現(xiàn)pop_left方法，取堆中最大元素，即優(yōu)先隊(duì)列中第一個(gè)元素。將數(shù)組中第一個(gè)元素與最后一個(gè)元素?fù)Q位置，刪除最后一個(gè)元素，然后將第一個(gè)元素下沉到合適的位置。

  def pop_left(self):
    self.swap(0, len(self) - 1)
    r = self.data.pop()
    self.sink_down(0)
    return r

如果想在初始化堆的時(shí)候，向構(gòu)造函數(shù)中傳入數(shù)據(jù)參數(shù)，則需要一次性將整個(gè)堆構(gòu)建完畢，而不能一個(gè)一個(gè)加入。實(shí)現(xiàn)也很簡(jiǎn)單，從最后一個(gè)非葉節(jié)點(diǎn)開(kāi)始，逐個(gè)執(zhí)行sink_down操作。

  def construct_heap(self):
    for i in range(len(self) // 2 - 1, -1, -1):
      self.sink_down(i)

這樣一個(gè)基本的堆的代碼就編寫(xiě)完畢了。

但是如果我們想要?jiǎng)討B(tài)的改變數(shù)據(jù)，當(dāng)前的堆就不能滿足我們的需求了，因?yàn)樗饕荒芸偸菢?biāo)識(shí)同一個(gè)數(shù)據(jù)，因?yàn)槎训慕Y(jié)構(gòu)是不斷調(diào)整的。我們需要使用索引堆。

在索引堆中，我們不在堆中直接保存數(shù)據(jù)，而是用在堆中存放數(shù)據(jù)的索引。

如果我們輸入的數(shù)據(jù)arr是 45 20 12 5 35。則arr[0]一直指向45，arr[1]一直指向20，因?yàn)槲覀冊(cè)谡{(diào)整堆結(jié)構(gòu)中實(shí)際調(diào)整的是索引數(shù)組，而不會(huì)改變真實(shí)存放數(shù)據(jù)的數(shù)組。

因此我們的代碼需要調(diào)整，首先在構(gòu)造函數(shù)中加入一個(gè)索引數(shù)組。下標(biāo)從0開(kāi)始，與存放數(shù)據(jù)的數(shù)組的下標(biāo)相對(duì)應(yīng)。

  def __init__(self, data=[]):
    self.data = data
    self.index_arr = list(range(len(self.data)))
    self.construct_heap()

然后將返回堆長(zhǎng)度的魔術(shù)函數(shù)也修改一下。

  def __len__(self):
    return len(self.index_arr)

調(diào)整一下之前定義的swap方法，原來(lái)是直接交換數(shù)據(jù)，現(xiàn)在交換索引。

 def swap(self, i, j):
    self.index_arr[i], self.index_arr[j] = self.index_arr[j], self.index_arr[i]

調(diào)整float_up以及sink_down中的相應(yīng)位置

  def float_up(self, i):
    while i > 0 and self.data[self.index_arr[i]] > self.data[self.index_arr[(i - 1) // 2]]:
      self.swap(i, (i - 1) // 2)
      i = (i - 1) // 2
      
  def sink_down(self, i):
    while i < len(self) // 2:
      l, r = 2 * i + 1, 2 * i + 2
      if r < len(self) and self.data[self.index_arr[l]] < self.data[self.index_arr[r]]:
        l = r
      if self.data[self.index_arr[i]] < self.data[self.index_arr[l]]:
        self.swap(i, l)

      i = l

當(dāng)append數(shù)據(jù)的時(shí)候，要相應(yīng)的更新index_arr

  def append(self, data):
    self.data.append(data)
    self.index_arr.append(len(self))
    self.float_up(len(self) - 1)

當(dāng)移出數(shù)據(jù)的時(shí)候，之前已經(jīng)提到過(guò)存放數(shù)據(jù)的數(shù)組，是按照append的順序進(jìn)行存儲(chǔ)的，平時(shí)操作只是對(duì)index_arr的順序進(jìn)行調(diào)整。

如果data_arr為 42 30 74 60 相應(yīng)的index_arr應(yīng)該為2 3 0 1

這時(shí)，當(dāng)我們popleft出最大元素時(shí)，data_arr中的74被移出后變成了42 30 60，數(shù)組中最大索引由3變成了2，如果索引數(shù)組中仍然用3這個(gè)索引來(lái)索引30會(huì)造成index溢出。74的索引為2，需要我們將索引數(shù)在2之后的都減1。

綜上，在刪除元素時(shí)，我們?cè)仁菍ata_arr中的首尾元素互換，再刪除尾部元素，再對(duì)頭部元素進(jìn)行sink_down操作。現(xiàn)在我們先換索引數(shù)組中首尾元素，再刪除索引數(shù)組尾部元素，此時(shí)尚未操作存放data的data_arr，因此索引數(shù)組剩余元素與data_arr的元素仍是一一對(duì)應(yīng)的。進(jìn)行sink_down操作，操作完成之后再刪除data_arr相應(yīng)位置元素。最后將index_arr中值大于原index_arr頭部元素值的減一。

  def pop_left(self):
    self.swap(0, len(self) - 1)
    r = self.index_arr.pop()
    self.sink_down(0)
    self.data.pop(r)

    for i, index in enumerate(self.index_arr):
      if index > r:
        self.index_arr[i] -= 1

    return r

索引堆增加了一個(gè)更新操作，可以隨時(shí)更新索引堆中的數(shù)據(jù)。更新時(shí)，先直接更新data_arr中相應(yīng)索引處的數(shù)據(jù)，然后在index_arr中，找到存放了data_arr中，剛被更新的數(shù)據(jù)的索引的索引位置，與刪除時(shí)一樣需要進(jìn)行一次遍歷。找到這個(gè)位置之后，由于無(wú)法確定與前后元素的大小關(guān)系，因此需要進(jìn)行一次float_up操作再進(jìn)行一次sink_down操作。

  def update(self, i, data):
    self.data[i] = data
    for index_index, index in enumerate(self.index_arr):
      if index == i:
        target = index_index

    self.float_up(target)
    self.sink_down(target)

可以很明顯看出，這個(gè)索引堆在插入元素時(shí)是比較快的，但是在刪除元素和更新元素時(shí)，為了查找相應(yīng)位置索引，都進(jìn)行了一次遍歷，這是很耗時(shí)的操作。為了能更快的找到index_arr中值為要更新的data_arr的相應(yīng)索引值得索引位置，我們?cè)俅伍_(kāi)辟一個(gè)新的數(shù)組to_index，來(lái)對(duì)index_arr進(jìn)行索引。

例如對(duì)于數(shù)組75 54 65 90

此時(shí)它的index_arr為3 0 2 1。當(dāng)要更新data[3]，即90這個(gè)元素時(shí)，現(xiàn)在要遍歷一遍index_arr來(lái)找到3這個(gè)位置，這個(gè)位置是0。我們要建立一個(gè)to_index，to_index[3]中存放的元素為0。

index_arr存放的元素分別為： 1 3 2 0。

先改變swap數(shù)組，在交換index_arr中元素時(shí)，也交換存放在to_index中的index_arr的索引。

 def swap(self, i, j):
    self.index_arr[i], self.index_arr[j] = self.index_arr[j], self.index_arr[i]
    self.to_index[self.index_arr[i]], self.to_index[self.index_arr[j]] = self.to_index[self.index_arr[j]], \
                                       self.to_index[self.index_arr[i]]

然后在update中，當(dāng)要更新位置為i的元素時(shí)，我們就不需要通過(guò)一次遍歷才能找到index_arr中該元素的索引，而是直接通過(guò)訪問(wèn)index_arr[i]即可訪問(wèn)index_arr中相應(yīng)索引

  def update(self, i, data):
    self.data[i] = data
    target = self.to_index[i]
    self.float_up(target)
    self.sink_down(target)

最后改變pop_left中相應(yīng)代碼，這時(shí)我們需要維護(hù)三個(gè)數(shù)組，data_arr，index_arr以及to_index。

仍然是首先將index_arr首位元素交換，并pop出尾部元素存放到i中。然后將頭部元素sink_down到相應(yīng)位置，然后將pop出data_arr索引i處的元素。然后pop出to_index中索引為i的元素，再將index_arr中索引溢出的元素進(jìn)行調(diào)整。

  def pop_left(self):
    self.swap(0, len(self) - 1)
    r = self.index_arr.pop()

    self.sink_down(0)
    self.data.pop(r)

    self.to_index.pop(r)
    for i in range(r, len(self)):
      self.index_arr[self.to_index[i]] -= 1

    return r

以上就是python實(shí)現(xiàn)對(duì)和索引堆的具體方式。希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。

最新評(píng)論