堆的簡單實現與代碼實現

堆的定義

在定義堆（heap）之前，先回顧一下完全二叉樹的定義：

• 完全二叉樹：除了最后一層的結點有可能沒有達到最大值外，其它層的結點值都達到最大值，此外最后一層的葉子結點會盡可能連續集中在左邊
  
• 堆的基本定義：堆是一種是基于樹的專用數據結構，一般是將一顆完全二叉樹的結點按照層序遍歷的順序存于數組中來實現的

堆具有以下幾個特性

• 在堆中，最高(或最低)優先級的元素始終都存儲在堆的根目錄(第一個儲存元素的位置)
• 堆中的父結點優先級總是大于等于(或小于等于)其子結點，但是其子結點并沒有大小順序之分，因此堆不能稱作一種順序數據結構，但是可以被當做是一種部分排序的儲存結構
• 堆的層次之間存在一個特殊關系，利用這個關系，可以代替索引的功能，找到對應的元素

堆的層次關系：

• 如果一個結點的位置為k ,則它的父結點的位置為[k/2],而它的兩個子結點的位置則分別為2k和2k+1。
• 這樣,在不使用指針的情況下.也可以通過計算數組的索引|在樹中上下移動:從a[k]向上一層,就令k等于k/2,向下一層就令k等于2k或2k+1。
  
  這里0索引不使用，因為索引從1開始會讓操作更方便

堆中插入元素append()使用的排序方法之一上浮swim()過程

堆中刪除最大元素的排序方法之一下沉sink()過程

下面用代碼實現堆，層次往下時元素的值從大到小排列

堆的操作方法

less()比較插入堆中的結點與當前節點的大小，輔助排序

swap()交換結點的值，一般與less合用，達到排序效果

append()向堆中尾部插入一個元素，其內部的swim()利用了堆的層次關系對元素進行上浮操作，實現父子結點間的大小排序

delete_max()刪除最大元素，并返回其最大值，其內部的sink()利用了堆的層次關系對元素進行下沉操作，實現父子結點間的大小排序

堆的Python代碼實現

import operatorclass Heap:def __init__(self):self.items = [None]self.N = 0 # The size of this heapdef less(self, i, j):return operator.lt(self.items[i], self.items[j])def swap(self, i, j):self.items[i], self.items[j] = self.items[j], self.items[i]def append(self, item):"""Append an element to its tail and do not use the index 0"""self.items.append(item)self.N += 1def swim(k):"""Adjust the element's position, keeping the heap sequential"""while k > 1:if self.less(int(k / 2), k):self.swap(int(k / 2), k)k = int(k / 2)swim(self.N)def delete_max(self):"""Delete the max value(the item where index=1) in this heap and return it"""if self.N < 1:return# Swap items[1] with items[-1]_max = self.items[1]self.swap(1, self.N)# Delete items[-1]del self.items[self.N]# The length of this heap subtract 1self.N -= 1# print(f"Length: {self.N}, Length-real: {len(self.items)-1}")# Sink() to adjust the sequence of this heapdef sink(k):"""Compare the current element with the max of its child nodes"""while 2 * k <= self.N:# Take the max child's indexindex_of_max_child = 2 * k if 2 * k + 1 > self.N else \(2 * k + 1 if self.less(2 * k, 2 * k + 1) else 2 * k)# When we found the position in where it should be, break the loopif self.less(index_of_max_child, k):break# Else, swap the current node's value with its max child node's valueself.swap(k, index_of_max_child)# Swap the current index with index_of_max_child, continue to do the while loopk = index_of_max_childsink(1)# Return the max valuereturn _max

代碼測試

if __name__ == '__main__':heap = Heap()heap.append('A')heap.append('B')heap.append('C')heap.append('D')heap.append('E')heap.append('F')heap.append('G')print(heap.N)# Iteratively delete the element in this heapres = heap.delete_max()while res:print(res, end=' ')res = heap.delete_max()

測試結果

7 G F E D C B A

是從小到大插入的元素，但是是依次取出最大元素，所以結果是從大到小排列（注意根據插入順序的不同，可能中間會有元素不是按照大小順序排放，但是整體是從大到小排列的）

總結

以上是生活随笔為你收集整理的数据结构之堆：堆的介绍与python实现——12的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。