什么是二叉堆
二叉堆（binary heap）是一种特殊的堆，二叉堆是完全二叉树或者是近似完全二叉树。二叉堆满足堆特性：父节点的键值总是保持固定的序关系于任何一个子节点的键值，且每个节点的左子树和右子树都是一个二叉堆。
当父节点的键值总是大于或等于任何一个子节点的键值时为“最大堆”。当父节点的键值总是小于或等于任何一个子节点的键值时为“最小堆”。
构建二叉堆
二叉堆一般用数组来表示。如果根节点在数组中的位置是 1，第 n 个位置的子节点分别在 2n 和 2n+1。因此，第 1 个位置的子节点在 2 和 3，第 2 个位置的子节点在 4 和 5。以此类推。这种基于 1 的数组存储方式便于寻找父节点和子节点。
如果存储数组的下标基于 0，那么下标为i的节点的子节点是 2i + 1 与 2i + 2；其父节点的下标是⌊floor((i − 1) ∕ 2)⌋。函数 floor(x)的功能是“向下取整”，或者说“向下舍入”，即取不大于 x 的最大整数（与“四舍五入”不同，向下取整是直接取按照数轴上最接近要求值的左边值，即不大于要求值的最大的那个值）。比如 floor(1.1)、floor(1.9)都返回 1。
在 Python 中，我们采用列表进行存储二叉堆。
def dowmAjust(num_list: list, parentIndex, lenght):
'''
下沉操作，非叶子节点不大于自己的子节点
:param num_list:
:param parentIndex:
:param lenght:
:return:
'''
temp = num_list[parentIndex]
childrenIndex = parentIndex * 2 + 1
while childrenIndex < lenght:
if childrenIndex + 1 < lenght and num_list[childrenIndex + 1] < num_list[childrenIndex]:
childrenIndex += 1
if temp <= num_list[childrenIndex]:
break
num_list[parentIndex] = num_list[childrenIndex]
parentIndex = childrenIndex
childrenIndex = 2 * childrenIndex + 1
num_list[parentIndex] = temp
def upAdjust(num_list: list, parentIndex, lenght):
'''
上浮操作，父节点不小于子节点
:param num_list:
:param parentIndex:
:param lenght:
:return:
'''
temp = num_list[parentIndex]
childrenIndex = parentIndex * 2 + 1
while childrenIndex < lenght:
if childrenIndex + 1 < lenght and num_list[childrenIndex + 1] > num_list[childrenIndex]:
childrenIndex += 1
if temp >= num_list[childrenIndex]:
break
num_list[parentIndex] = num_list[childrenIndex]
parentIndex = childrenIndex
childrenIndex = 2 * childrenIndex + 1
num_list[parentIndex] = temp
def build_binary_Heap(num_list: list,Flag=True):
'''
构建二叉堆
:param num_list:
:return:
'''
no_leaf_node_index = (len(num_list) - 2) // 2
while no_leaf_node_index >= 0:
if Flag:
dowmAjust(num_list, no_leaf_node_index, len(num_list))#构建最小堆
else:
upAdjust(num_list, no_leaf_node_index, len(num_list))#构建最大堆
no_leaf_node_index -= 1
if __name__ == '__main__':
num_list = [7, 1, 3, 10, 5, 2, 8, 9, 6]
build_binary_Heap(num_list,False)
print(num_list)
插入节点
在数组的最末尾插入新节点。然后自下而上调整子节点与父节点（称作 up-heap 或 bubble-up, percolate-up, sift-up, trickle up, heapify-up, cascade-up 操作）：比较当前节点与父节点，不满足“堆性质”则交换。从而使得当前子树满足二叉堆的性质。时间复杂度为 O(log n)。
def addNode(num_list:list, num:int):
length = len(num_list)
if length <= 1:
num_list.append(num)
print("当前列表仅有两个值，无法判断属于最大堆或最小堆！")
return
first_num = num_list[0]
num_list.append(num)
parentIndex = ((length+1)-2)//2
childrenIndex = length
while childrenIndex > 0:
if first_num == max(num_list): #判断该二叉堆是否是最大堆
if num_list[parentIndex] >= num_list[childrenIndex]:
break
elif first_num == min(num_list): # 判断该二叉堆是否是最小堆
if num_list[parentIndex] <= num_list[childrenIndex]:
break
num_list[childrenIndex],num_list[parentIndex] = num_list[parentIndex],num_list[childrenIndex]
childrenIndex = parentIndex
index = (childrenIndex-2)//2
parentIndex = index if index >=0 else 0
删除节点
删除根节点用于堆排序。
对于最大堆，删除根节点就是删除最大值；对于最小堆，是删除最小值。然后，把堆存储的最后那个节点移到填在根节点处。再从上而下调整父节点与它的子节点：对于最大堆，父节点如果小于具有最大值的子节点，则交换二者。这一操作称作 down-heap或bubble-down, percolate-down, sift-down, trickle down, heapify-down, cascade-down,extract-min/max 等。直至当前节点与它的子节点满足“堆性质”为止。
def deleteNode(num_list:list):
'''
删除根节点用于堆排序
对于最大堆，删除根节点就是删除最大值；对于最小堆，是删除最小值。然后，把堆存储的最后那个节点移到填在根节点处。再从上而下调整父节点与它的子节点
:param num_list:
:param num:
:return:
'''
length = len(num_list)
if length <= 1:
num_list = []
first_num = num_list[0]
num_list[0] = num_list[-1]
num_list.remove(num_list[-1])
if first_num == max(num_list): # 判断该二叉堆是否是最大堆
build_binary_Heap(num_list,False)
elif first_num == min(num_list): # 判断该二叉堆是否是最小堆
build_binary_Heap(num_list)
基础排序
有了堆的基本操作，实现堆的排序就比较简单了，用最大堆实现升序排序。
将最大堆的根节点取出，放入到新的列表中，同时删除该值；把最后一个叶子节点放在根节点的位置，然后对根节点做“上浮”操作，保证根节点为当前所有节点中的最大值。
def heapSort(num_list:list):
'''
输入的二叉堆是最大堆，最后输出从小到大的有序集合
:param num_list:
:return:
'''
sorted_list = []
length = len(num_list)
if length <= 1:
return num_list
p = -1
while length-1 > 0:
sorted_list.insert(0,num_list[0])
num_list[0],num_list[p] = num_list[p],num_list[0]
upAdjust(num_list,0,length-1)#上浮操作，保证根节点为当前二叉堆中最大值
length -= 1
p -= 1
return num_list
堆排序分为两步：
- 将无序列表构建为二叉堆。
- 循环删除堆顶元素，并将尾部节点移动堆顶，调整堆产生新的堆顶。
堆排序的空间复杂度为 O(1)，因为没有开辟额外的集合空间。
计算时间复杂度。因为第一步把无序列表构建成二叉堆，这一步的时间复杂度为 O(n)；第二步需要进行 n-1 次循环，每次循环调用一次 upAdjust 方法，所以第二步的计算规模是 (n-1)×logn，时间复杂度为 O(nlogn)。
两个步骤是并列关系，所以整体的时间复杂度是 O(nlogn)。
这里多说几句，堆排序和快速排序相比，有什么区别和联系？
- 相同点：堆排序和快速排序的平均时间复杂度都是 O(nlogn)，都是不稳定排序。
- 不同点：快速排序的最坏时间复杂度是 O(n^2)，而堆排序的最坏时间复杂度稳定在 O(nlogn)；此外快速排序和非递归方法的平均空间复杂度都是 O(logn)，而堆排序的空间复杂度是 O(1)。
本文作者为hresh，转载请注明。