数据结构：堆

这一篇博客将介绍堆

堆

堆是一种满足特定条件的完全二叉树，分为

大顶堆(max heap)：任意节点的值其子节点的值
小顶堆(min heap)：任意节点的值其子节点的值

堆的术语

堆的根节点称为堆顶，底层最靠右的节点称为堆底

常用操作

许多编程语言提供了一种叫做优先队列的抽象数据结构，定义为具有优先级排序的队列

堆通常用作实现优先队列，大顶堆相当于元素按从大到小顺序出队的优先队列。

push()：元素入堆，时间复杂度为
pop()：堆顶元素出堆，时间复杂度为
peek()：访问堆顶元素（大/小顶堆分别为最大/小值），时间复杂度为
size()：获取堆的元素数量，时间复杂度为
isEmpty()：判断堆是否为空，时间复杂度为

实际应用中，可直接使用编程语言提供的堆类(或优先队列类)

Python
C++

# Python 的 heapq 模块默认实现小顶堆
# 将元素取负后再入堆，可以将大小关系颠倒，从而实现大顶堆
# 使用flag变量确定是大顶堆还是小顶堆

# 初始化小顶堆
min_heap, flag = [], 1

# 初始化小顶堆
max_heap, flag = [], -1

# 入堆，将入堆值乘上flag，用于对应大顶堆
heapq.heappush(max_heap, flag * 1)

peek = flag * max_heap[0]

val = flag * heapq.heappop(max_heap)

size = len(max_heap)

is_empty = not max_heap

# 输入列表并建堆
min_heap = [1, 3, 2, 5, 4]
heapq.heapify(min_heap)

/*  priority_queue是STL容器，表示优先队列
    参数依次是：1.队列中元素类型 2.底层容器的类型
    3.一个比较器(comparator)函数对象

    priority_queue默认使用<操作符来比较元素大小，greater<int>使用>操作符来比较元素大小
*/

// 初始化小顶堆
priority_queue<int, vector<int>, greater<int>> minHeap;

// 初始化大顶堆
priority_queue<int, vector<int>, less<int>> maxHeap;

maxHeap.push(1);
maxHeap.push(3);

int peek = maxHeap.top();

maxHeap.pop();

int size = maxHeap.size();

bool isEmpty = maxHeap.epmty();

// 输入列表并建堆
vector<int> input{1, 3, 2, 5, 4};
priority_queue<int, vector<int>, greater<int>> minHeap(input.begin(), input.end());

堆的实现

堆的存储与表示

堆是一种完全二叉树，完全二叉树非常适合用数组来表示，因此可以采用数组来存储堆。节点指针通过索引映射公式来实现

def left(self, i):
    return 2 * i + 1

def right(self, i):
    return 2 * i + 2

def parent(self, i):
    return (i - 1) // 2

int left(int i) {
    return 2 * i + 1;
}

int right(int i) {
    return 2 * i + 2;
}

int parent(int i) {
    return (i - 1) / 2;
}

int left(int i) {
    return 2 * i + 1;
}

int right(int i) {
    return 2 * i + 2;
}

int parent(int i) {
    return (i - 1) / 2;
}

访问堆顶元素

def peek(self):
    return self.max_heap[0]

int peek(){
    return max_heap[0];
}

int peek(MaxHeap* maxHeap){
    return maxHeap->data[0];
}

元素入堆

首先，将元素添加到堆底，此时堆的性质可能被破坏
然后，需要修复从插入节点到根节点的路径上的各个节点，这个操作称为堆化(heapify)。从入堆节点开始，从底至顶执行堆化，比较插入节点与其父节点，若违反堆的性质，进行交换，继续此操作。直到越过根节点或遇到无需交换的节点时结束
设节点总数为n，则树的高度为。因此，堆化操作的循环轮数最多为，元素入堆操作的时间复杂度为

def push(self, val):
    self.max_heap.append(val)
    self.sift_up(self.size() - 1)

def sift_up(self, i):
    # 用于最大堆的辅助函数
    while True:
        p = self.parent(i)
        if p < 0 or self.max_heap[i] <= self.max_heap[p]:
            break
        self.swap(i, p)
        i = p

void push(int val){
    maxHeap.push_back(val);
    siftUp(size() - 1);
}

void siftUp(int i){
    while(true){
        int p = parent(i);
        if(p < 0 || maxHeap[i] <= maxHeap[p]){
            break;
        }
        swap(maxHeap[i], maxHeap[p]);
        i = p;
    }
}

void push(MaxHeap* maxHeap, int val){
    if(maxHeap->size == MAX_SIZE){
        printf("heap is full!");
        return;
    }
    maxHeap->data[maxHeap->size] = val;
    maxHeap->size++;

    siftUp(maxHeap, maxHeap->size - 1);
}

void siftUp(MaxHeap* maxHeap, int i){
    while(true){
        int p = parent(i);
        if(i < 0 || maxHeap->data[i] <= maxHeap->data[p]){
            break;
        }
        swap(maxHeap, i, p);
        i = p;
    }
}

堆顶元素出堆

堆顶元素是根节点，存储在列表首个位置。如果直接从列表中删除首元素，二叉树中所有节点饿索引都会发生变化，堆化修复十分困难。为减少索引变动，操作步骤如下

交换堆顶元素(根节点)与堆底元素(最右叶节点)
将堆底(原来的堆顶)从列表删除
从根节点开始，从顶至底执行堆化。对于大顶堆来说，将根节点与其两个子节点比较，将最大(小)子节点与根节点交换，循环该操作，直到越过叶节点或遇到无需交换的节点时结束

def pop(self):
    if self.is_empty():
        raise IndexError("堆为空")
    self.swap(0, self.size() - 1)
    val = self.max_heap.pop()
    self.sift_down(0)
    return val

def sift_down(self, i):
    # 用于大顶堆的辅助函数
    while True:
        l, r, ma = self.left(i), self.right(i), i
        if l < self.size() and self.max_heap[l] > self.max_heap[ma]:
            ma = l
        if r < self.size() and self.max_heap[r] > self.max_heap[ma]:
            ma = r
        # 若节点 i 最大 或 l, r越界，则无需继续堆化
        if ma == i:
            break
        self.swap(i, ma)
        i = ma

void pop(){
    if(isEmpty()){
        throw out_of_range("堆为空");
    }
    swap(maxHeap[0], maxHeap[size() - 1]);
    maxHeap.pop_back();
    siftDown(0);
}

void siftDown(int i){
    int l, r, ma;
    while(true){
        l = left(i);
        r = right(i);
        ma = i;
        if(l < size() && maxHeap[l] > maxHeap[ma]){
            ma = l;
        }
        if(r < size() && maxHeap[r] > maxHeap[ma]){
            ma = r;
        }
        if(ma == i){
            break;
        }
        swap(maxHeap[i], maxHeap[ma]);
        i = ma;
    }
}

void pop(MaxHeap* maxHeap){
    if(isEmpty(maxHeap)){
        printf("heap is empty!");
        return;
    }
    swap(maxHeap, 0, size(maxHeap) - 1);
    siftDown(maxHeap, 0);
}

void siftDown(MaxHeap* maxHeap, int i){
    int l, r, ma;
    while(true){
        l = left(i);
        r = right(i);
        ma = i;
        if (l < size(maxHeap) && maxHeap->data[l] > maxHeap->data[ma]){
            ma = l;
        }
        if (r < size(maxHeap) && maxHeap->data[r] > maxHeap->data[ma]){
            ma = r;
        }
        if (ma == i){
            break;
        }
        swap(maxHeap, i, ma);
        i = ma;
    }
}

常见应用

优先队列：堆常用于实现优先队列，入队和出队操作的时间复杂度为，建堆操作为
堆排序：用一组数据建立一个堆，然后不断出堆，即可得到有序数据
获取最大的k个元素：一个经典的算法问题

建堆

使用一个列表的所有元素来构建一个堆的过程被称为建堆操作

实现一: 借助入队操作(每个元素进行上浮)

创建一个空堆
遍历列表，依次对每个元素入堆
该建堆方法的时间复杂度为
，也就是

自顶自下逐渐满足堆的性质，因此是自顶向下建堆

实现二: 通过遍历堆化(每个非叶节点进行下沉)

将列表所有元素原封不动添加到堆中，此时堆的性质可能未被满足
倒序遍历堆(层序遍历的倒序)，依次对每个非叶节点执行从顶至底堆化

每当堆化一个节点，以该节点为根节点的子树就形成一个合法的子堆。同时该过程按层序遍历的倒序进行，堆是自下而上地被构建

之所以选择倒序遍历，是因为这样能保证当前节点的所有子树已经是合法子堆，这样堆化当前节点才有效

叶节点没有子节点，天然就是合法子堆，无需堆化

自底向上逐渐满足堆的性质，因此整体是自底向上建堆。而每个迭代中是从顶至底建堆

def __init__(self, nums):
    self.max_heap = nums
    for i in range(self.parent(self.size() - 1), -1, -1):
        self.sift_down(i)

MaxHeap(vector<int> nums){
    maxHeap = nums;
    for (int i = parent(size() - 1); i >=0; i--){
        siftDown(i);
    }
}

MaxHeap* newMaxHeap(int* nums, int size){
    // 底层数据结构为完全二叉树的数组存储
    MaxHeap* maxHeap = (MaxHeap*)malloc(sizeof(MaxHeap));
    maxHeap->size;
    memcpy(maxHeap->data, nums, size * sizeof(int));
    for(int i = parent(size - 1); i >=0; i--){
        siftDown(i);
    }
    return maxHeap;
}

实现二复杂度分析

假设给定一个节点数量为n，高度为h的完美二叉树，该假设不会影响计算结果的正确性

节点从顶至底堆化的最大迭代次数等于该节点到叶节点的距离，也就是其节点高度。因此我们可以将各层的 $节点数量节点高度$ 求和，得到所有节点的堆化迭代次数的总和

可以得到

对于完美二叉树，，因此

因此实现二建堆的时间复杂度为，非常高效

Top-K问题

Top-K问题是一个经典算法问题，题目如下

给定一个长度为n的无序数组nums，请返回数组中前k大的元素

方法一: 遍历选择

进行k轮遍历，分别在每轮中提取第1、2、…、k大的元素，时间复杂度为

此方法只适用于的情况，当与接近时，时间复杂度趋于，非常耗时

当时，等价于选择排序

方法二：排序

先对数组nums排序，再返回最右边的k个元素，时间复杂度为。但是该方法超额完成了任务

方法三：堆

初始化一个小顶堆
将数组的前k个元素依次入堆
从第k+1个元素开始，若当前元素大于堆顶元素，将堆顶元素出堆，当前元素入堆
遍历结束后，堆中保存的就是最大的k个元素

总共执行轮入堆和出堆，堆的最大元素个数为，因此时间复杂度为。当较小时，趋于，当k较大时，不超过

这个方法还适用于动态数据流。不断加入数据时，持续维护堆内的元素，从而实现最大（最小）个元素的动态更新

Python
C++

def top_k_heap(nums, k):
    heap = []
    for i in range(k):
        heapq.heappush(heap, nums[i])
    for i in range(k, len(nums)):
        if nums[i] > heap[0]:
            heapq.heappop(heap)
            heapq.heappush(heap, nums[i])
    return heap

priority_queue<int, vector<int>, greater<int>> topKHeap(vector<int> &nums, int k){
    priority_queue<int, vector<int>, greater<int>> heap;
    for (int i = 0; i < k; i++){
        heap.push(nums[i]);
    }
    for (int i = k; i < nums.size(); i++){
        if (nums[i] > heap[0]){
            heap.pop();
            heap.push(nums[i]);
        }
    }
    return heap;
}

敖炜的博客