二叉堆(Binary Heap)
2021-01-12 本文已影响0人
茂财
二叉堆这个数据结构有点意思，自己做了个总结，内容结构如下：
-
二叉堆性质
-
二叉堆操作
-
应用
二叉堆性质：
堆（Heap）是一个可以被看成近似完全二叉树的结构，具有完全二叉树的特性：
- 缺少的叶子节点总是位于右子节点
- n个节点的完全二叉树高度：k=⌊ log2n⌋（向上取整）
- 从1开始按层序编号，那么第i个节点有如下性质：
- 其左子节点索引是：2i
- 其又子节点索引是：2i+1
- 其父节点索引为 ： i // 2
同时具有堆的特性：
- 堆顶元素就是最值，O(1)时间就能优先拿到
- 从根节点（堆顶）到堆中每一个节点都是一个有序序列。
-
存储方式可以用线性的数组来实现，实现简单易操作，不过要注意数组下标从0开始，这个位置预留占位，节点的索引从1开始编号。
2.png
binarytree.png
二叉堆操作：
-
BinaryHeap()：创建一个空的二叉堆对象 -
insert(key)：将新元素加入到堆中 -
findMin()：返回堆中的最小项，最小项仍保留在堆中 -
delMin()：返回堆中的最小项，同时从堆中删除 -
isEmpty()：返回堆是否为空 -
size()：返回堆中节点的个数 -
buildHeap(lst)：从一个包含节点的列表里创建新堆
# 直接导入Pythonds包使用其提供的有关堆的数据结构。
from pythonds.trees import BinaryHeap
bheap=BinaryHeap()
bheap.insert(5)
#用list来实现对堆的操作
class BinaryHeap(object):
"""定义一个二叉堆"""
def __init__(self):
self.heapList = [0] # 第一个堆元素从1开始编号，索引为0占位不用
self.currentSize = 0
def percolateUP(self, i):
'''将第i个元素上浮到合适位置'''
while i // 2 > 0:
if self.heapList[i] < self.heapList[i // 2]:
self.heapList[i], self.heapList[
i // 2] = self.heapList[i // 2], self.heapList[i]
else:
break
i = i // 2
def percolateDown(self, i):
'''将第i个元素下沉到合适位置'''
while (2 * i) <= self.currentSize:
minIndex = self.minChild(i)
if self.heapList[i] > self.heapList[minIndex]:
self.heapList[i], self.heapList[
minIndex] = self.heapList[minIndex], self.heapList[i]
else:
break
i = minIndex
def minChild(self, i):
'''返回第i个元素左右子节点中最小值'''
if (2 * i + 1) > self.currentSize:
return 2 * i # 只有一个子节点（左子节点）
elif self.heapList[2 * i] < self.heapList[2 * i + 1]:
return 2 * i
else:
return 2 * i + 1
def insert(self, key):
'''将新元素加入到堆中'''
self.heapList.append(key)
self.currentSize = self.currentSize + 1
self.percolateUP(self.currentSize) # 新值上浮
def findMin(self):
'''返回堆中的最小项，最小项仍保留在堆中'''
return heapList[1]
def delMin(self):
'''返回堆中的最小项，同时从堆中删除'''
result = self.heapList[1]
# 将最后一个元素换到堆顶并删除堆顶元素
self.heapList[1] = self.heapList.pop()
self.currentSize = self.currentSize - 1
self.percolateDown(1) # 将堆顶元素下沉
return result
def isEmpty(self):
'''返回堆是否为空'''
return len(heapList) == 1
def size(self):
'''返回堆中节点的个数'''
return len(heapList) - 1
def printHeap(self):
print(self.heapList[1:])
def buildHeap(self, lst):
'''从一个包含节点的列表里创建新堆,用下沉法将时间复杂度控制在O(n)'''
self.currentSize = len(lst)
i = self.currentSize // 2 #从最后一个节点的父节点开始过滤下沉！
self.heapList = [0] + lst[:]
while i > 0:
self.percolateDown(i)
i = i - 1
self.printHeap()
应用之一-----------------优先队列：
可以在O(1)时间拿到最值，获取最优解，实现对VIP或者进程的优先级等操作
pic_19.png
