堆

堆，是一个类似于树的数据结构，其中子节点们与其父节点有一个排序的关系。

二叉堆能够表示为使用一个列表或者数组来组织，因此元素N的子节点位于2N+1和 2N+2（对于基于0的索引）。这样的布局允许在原来位置重置堆，因此没有必要在添加和删除元素的时候重置过多的内存空间。

堆的存储结构基本操作 up down heapify pop & push & modify sort 完整代码练习题

堆的存储结构

逻辑结构是完全二叉树，存储结构为数组。数组下标对应完全二叉树如下图：

基本操作

堆的基本操作包括

heapify() 将数组转为小顶堆

pop(idx) 删除下标 idx 的元素，idx = 0 时，弹出堆顶元素

push(val) 向堆中添加元素

modify(idx, val)修改idx的值为 val

sort() 堆排序

以上基本操作均可由 up down 两个操作组合实现。

up

即上浮操作，把下面较小的值上浮到上层。只需要和自己的父节点比较


def up(self, idx):
		if idx <= 0:
				return
		if self.nums[idx] < self.nums[(idx - 1) // 2]:
				self.nums[idx], self.nums[(idx-1)//2] = self.nums[(idx-1)//2], self.nums[idx]
				self.up((idx-1)//2)

down

下沉操作，即把上层较大的值下沉下去。需要将当前节点个两个子节点比较，然后将当前节点和最小的子节点交换，然后继续对交换的子节点执行down操作。

和子节点比较的时候，初始化一个暂存值，用来保存当前节点、左子节点、右子节点着三个节点最小值的下标，然后任意一点


def down(idx):
		min_idx = idx
		if idx*2 + 1 < len(self.nums) and self.nums[min_idx] > self.nums[idx*2+1]:
				min_idx = idx * 2 + 1
		if idx * 2 + 2 < len(self.nums and self.nums[min_idx] > self.nums[idx*2+2]:
				min_idx = idx*2 + 2
		
		if min_idx != idx:
				self.nums[idx], self.nums[min_idx] = self.nums[min_idx], self.nums[idx]
				self.down(min_idx)

heapify

heapify 操作即把数组转化为最小堆。转化为最小堆需要每颗子树都满足父节点大于子节点。

一种朴素的思路是将数组一个个push进去，但是这样时间复杂度为nlog(n)。

还有一种O(n)复杂度的做法是：从len(nums) // 2 的位置开始执行 down 操作，一直执行到下标 0。


def heapify(self):
    for idx in range(len(self.nums) // 2, -1, -1) :
        self.down(idx)

pop & push & modify

pop ，push, modify 操作是很类似的：

pop 操作是弹出一个元素，因为是数组操作，所以把该元素和最末尾的元素交换，然后弹出最后一个元素，最后把交换过来的最后一个元素执行 up down 操作。本质上此处只需要一个操作，但是需要判断以下当前值和原先值的大小，为了简化代码，所以直接都写上去，反正最终只会执行一个。

push 操作即新添加一个元素，新添加的元素肯定在数组末尾，然后对新添加的元素执行 up 操作即可。

modify操作，修改完，直接 up down操作即可。

sort

每次弹出堆顶元素，弹出的顺序即为递增顺序。弹出n次，所以是nlog(n)复杂度

完整代码


class heap:
    def __init__(self, nums = []):
        self.nums = nums
    
    def heapify(self):
        """初始化一个堆，当然可以通过 一个个添加元素到堆中，但这样就是nlogn的复杂度
        可以采用如下的方式，将时间复杂度降到 O(n)
        """
        for idx in range(len(self.nums) // 2, -1, -1) :
            self.down(idx)

    def up(self, idx):
        # 当一个数变小之后就往上调
        if idx <= 0:
            return
        if self.nums[idx] < self.nums[(idx-1) // 2]:
            self.nums[idx], self.nums[(idx-1)//2] = self.nums[(idx-1)//2], self.nums[idx]
            self.up((idx-1) // 2)

        return
    def down(self, idx):
        # 当一个数字边大之后就往下调,选择和较小的子节点交换
        
        # 用来记录最小值的下标
        min_idx = idx 
        if idx * 2 + 1  < len(self.nums) and self.nums[idx*2+1] < self.nums[min_idx]:
            min_idx = idx * 2 + 1
        if idx *2 + 2 < len(self.nums) and self.nums[idx*2+2] < self.nums[min_idx]:
            min_idx = idx * 2 + 2

        if min_idx != idx:
            self.nums[idx], self.nums[min_idx] = self.nums[min_idx], self.nums[idx]
            self.down(min_idx)           
           
            
    def add(self, x):
        # 插入操作
        # 插到末尾，不断的 up 上去
        self.nums.append(x)
        self.up(len(self.nums)-1)

    def pop_min(self):
        # 删除最小值 (删除最小值)
        # 把最后一个元素和第一个元素交换，然后删掉最后一个元素，再把第一个元素 down 下来
        res = self.nums[0]
        self.nums[0] = self.nums[-1]
        self.nums.pop() 
        self.down(0)
        return res

    def pop(self, idx=0):
        # 删除任意一个元素, 如果 idx = 0, 就是最小值
        # 做法和 删除最小元素相似
        res = self.nums[idx]
        self.nums[idx] = self.nums[-1]
        self.nums.pop()
        # 这里把末位元素放到 idx 位置之后，应该是根据元素大小判断down 还是 up，
        # 但是可以不用手动判断，因为 down 或者 up 的代码里面已经有判断了
        self.down(idx)
        self.up(idx)
        return res
        
    def modify(self, idx, val):
        if idx >= len(self.nums):
            self.nums.append(val)
            self.up(len(self.nums)-1)
        else:
            self.nums[idx] = val
            self.down(idx)
            self.up(idx)

    def sort(self):
        temp_nums = []
        while self.nums:
            temp_nums.append(self.pop(0))
        self.nums = temp_nums

练习题

130 · 堆化 - LintCode