用python构建大根堆

• 堆的定义
• • 正确的堆
  • 错误的堆
• 构建堆结构
• • 基本操作
  • • 上滤
    • • 演示
    • 下滤
    • • 演示
  • 构建堆

堆的定义

• 堆是一棵完全二叉树，即除了最后一层外，其它各层的节点数都达到最大个数，且最后一层的所有节点都连续集中在最左边。

正确的堆

错误的堆

常见的堆有大根堆小根堆

• 大根堆的父节点严格大于子节点
• 小根堆的子节点严格小于子节点

构建堆结构

由于堆是完全二叉树，因此可以使用数组来储存堆的层序遍历。
如该二叉树可以用下列数组来储存

[18,13,15,6,3,13,5]

使用数组表示堆有一个好处，就是对于每一个下标为i的非叶子节点，它的左子节点下标为2i+1,右子节点下标为2i+2(如果右子节点存在的话)

基本操作

以_大根堆_为例，堆有两个常见的操作，分别为上滤和下滤。

上滤

当堆顶元素被删除时，将堆底元素插入堆顶，当插入元素小于子节点时，堆的堆序性被破坏，将插入元素与子节点的较大值交换顺序。

继续此操作直至该堆成为一个合法的大根堆为止。

演示

下滤

当堆底插入新元素时，如果新插入元素大于其父元素，堆序性被破坏，此时应将插入元素与其父元素交换位置，直至满足堆序性。

演示

构建堆

由以上可知，在插入堆的时候，使用下滤维护堆序性，在删除堆顶元素时，使用上滤来维护堆序性。

于是将一个数组转化为大根堆或小根堆的思路是，从最后一个非叶子节点向根节点出发，依次进行下滤，这样就可以得到一个满足堆排序的数组。

然后每次弹出根元素后进行上滤操作维护堆序性，就可以实现堆排序

下面用python算法实现一个大根堆

def max_heapify(index,start,end):#上滤    root = start    while True:        child = root * 2 + 1        if child > end:            break        #选择子节点较大值        elif child + 1 <= end and nums[index+child] < nums[index+child + 1]:            child += 1            if nums[index+child] > nums[index+root]:                nums[index+root], nums[index+child] = nums[index+child], nums[index+root]                root = child            else:                returndef create_maxheap(index=0):    m = len(nums) - index    start = m // 2 - 1    for i in range(start, - 1, -1):        max_heapify(index, i,len(nums) - 1-index)

小根堆的实现方式与其类似，就不过多赘述了。