【数据结构】 二叉堆

什么是数据结构？

结构定义+结构操作

结构定义是定义了这种数据结构具有的性质，结构操作的目的是为了维护这种性质。

那么二叉堆或者说优先队列有什么性质呢？

首先二叉堆是一颗完全二叉树，其次对于大顶堆来说每个根节点的值都大于孩子节点的值，这意味着，你可以用0（1）的时间获得二叉堆中所有数的最大值。

为了维护二叉堆的性质，我们需要定义插入和删除两种o（log n）的操作。

在二叉堆数据的存储上，采用数组来存储，

因为完全二叉树是可以按层次顺序存入到一个数组中去的。且具有 i * 2 为i节点的左子树，i*2 +1 为i节点的右子树这个性质。那么数组就不是一个数组了而是一颗树了

注意，思维上的转变。

二叉堆的具体实现

二叉堆结构定义

typedef struct Heap{
    int *data;
    int n;// 指向堆的最后一个元素
    int size;// 堆的大小
}Heap;

// 显示堆的大小的
#define size(h) h->size

// 初始化一个堆
Heap* init(int n){
    Heap *h = (Heap *)malloc(sizeof(Heap));
    h->n = 0;
    size(h) = n+1;
    h->data = (int*)malloc(sizeof(int)*size(h));
    return h;
}

// 释放一个堆
void clear(Heap *h){
    if(h == NULL)return;
    free(h->data);
    free(h);
    return;
}

二叉堆的结构操作

插入一个元素

1. 插入到堆的末尾
2. 向上调整，维护堆的性质
   1. 比较当前节点和父节点的值
   2. 如果比父节点值大就交换父节点，更新当前节点为父节点，回到1
   3. 结束调整

#define V(h,ind) h->data[ind]
// 向上调整
void up(Heap*h){
    int ind = h->n;
    while(ind >= 1 && V(h,ind) > V(h,ind >> 1)){
        swap(V(h,ind),V(h,ind<<1));
        ind >>= 1;
    }
}

void push(Heap *h,int val){
    h->data[++h->n] = val;
    up(h);
}

删除堆顶元素

1. 堆顶元素赋值为堆尾元素，完成删除
2. 调整堆，维护性质
   1. 选取当前节点左右节点中较大的与当前节点比较
   2. 当前节点小就交换，更新当前节点
   3. 结束循环

// 向下调整
void down(Heap*h,int ind,int end){
    int temp;
    while(ind << 1 <= end){
        temp = ind <<1;
        if(temp < end && V(h,temp) < V(h,temp+1))++temp;
        if(V(h,temp) > V(h,ind)){
            swap(V(h,temp),V(h,ind));
            ind = temp;
        }else break;
    }
}

void pop(Heap *h){
    h->data[1] = h->data[h->n];
    down(h,1,--h->n);
}

获得堆顶元素

#define top(h) h->data[1]

c++ 优先队列使用（二叉堆）

template< class T,
class Container = std::vector<T>,
class Compare = std::less<typename Container::value_type>

>class priority_queue ;

A priority queue is a container adaptor that provides constant time lookup of the largest (by default) element, at the expense of logarithmic insertion and extraction.(以对数插入和提取为代价。)

A user-provided Compare can be supplied to change the ordering, e.g. using std::greater<T> would cause the smallest element to appear as the top().

Working with a priority_queue is similar to managing a heap in some random access container, with the benefit of not being able to accidentally invalidate the heap.

Member functions

#include <functional>
#include <queue>
#include <vector>
#include <iostream>
 
template<typename T> void print_queue(T& q) {
    while(!q.empty()) {
        std::cout << q.top() << " ";
        q.pop();
    }
    std::cout << '\n';
}
 
int main() {
    // 默认大顶堆
    std::priority_queue<int> q;
 
    for(int n : {1,8,5,6,3,4,0,9,7,2})
        q.push(n);
 
    print_queue(q);
 
    std::priority_queue<int, std::vector<int>, std::greater<int> > q2;
    
    // 小顶堆
    for(int n : {1,8,5,6,3,4,0,9,7,2})
        q2.push(n);
 
    print_queue(q2);
}

https://en.cppreference.com/w/cpp/container/priority_queue

java 二叉堆的使用

<https://docs.oracle.com/javase/10/docs/api/java/util/PriorityQueue.html>

二叉堆的应用

703. 数据流中的第K大元素

这个体现了二叉堆的一个性质，

对于容纳了k个元素的小顶堆来说：

1. 堆顶的最小的元素
2. 堆内总共有k个元素，且都大于堆顶

那么在一个新的元素出现时，如果堆内元素小于k就直接将新元素压入堆，否则比较该元素是否是大于堆顶的元素，是就入堆，否则就不管了。

这时，堆顶元素就是一个动态的分界线，始终动态的是k个元素中最小的元素，注意这个性质。

那么这样，我们就维护了一个结构可以求数据流中第k个大的元素了。

然后之所以用c写是为了练习实现堆的操作。

typedef struct Heap{
    int *data;
    int n,size;
}Heap;
#define swap(a,b){\
    __typeof(a) __temp = a;\
    a = b; b = __temp;\
}
Heap* init(int n){
    Heap *h = (Heap *)malloc(sizeof(Heap));
    h->n = 0;
    h->size = n+1;
    h->data = (int*)malloc(sizeof(int)*h->size);
    return h;
}
#define V(h,ind) h->data[ind]
// 向上调整
void up(Heap*h){
    int ind = h->n;
    while(ind >> 1 >= 1 && V(h,ind) < V(h,ind >> 1)){
        swap(V(h,ind),V(h,ind >> 1));
        ind >>= 1;
    }
}

void push(Heap *h,int val){
    h->data[++h->n] = val;
    up(h);
}

// 向下调整
void down(Heap*h,int ind,int end){
    int temp = ind << 1;
    while(temp <= end){
        if(temp < end && V(h,temp) > V(h,temp+1))++temp;
        if(V(h,temp) < V(h,ind)){
            swap(V(h,temp),V(h,ind));
            ind = temp;
            temp = ind <<1;
        }else break;
    }
}

void pop(Heap *h){
    h->data[1] = h->data[h->n];
    down(h,1,--h->n);
}
#define top(h) h->data[1]
void clear(Heap *h){
    if(h == NULL)return;
    free(h->data);
    free(h);
    return;
}

typedef struct {
    Heap * heap;
} KthLargest;

int kthLargestAdd(KthLargest* obj, int val);

KthLargest* kthLargestCreate(int k, int* nums, int numsSize) {
    KthLargest * kl = (KthLargest*) malloc(sizeof(KthLargest));
    kl -> heap = init(k);
    for(int i = 0;i <numsSize;++ i){
        kthLargestAdd(kl,nums[i]);
    }
    return kl;
}

int kthLargestAdd(KthLargest* obj, int val) {
    if(obj->heap->n+1< obj->heap->size){
        push(obj->heap,val);
    }else if(val > top(obj->heap)){
        pop(obj->heap);
        push(obj->heap,val);
    }
    return top(obj->heap);
}

void kthLargestFree(KthLargest* obj) {
    clear(obj->heap);
    free(obj);
}

295. 数据流的中位数

这个就是维护两个堆，形成对顶堆，从而动态维护了 第 n/2 大的元素，和 第 n/2 小的元素

class MedianFinder {
private:
    priority_queue<int,vector<int>,greater<int>> minHeap;
    priority_queue<int,vector<int>,less<int>> maxHeap;
public:
    /** initialize your data structure here. */
    MedianFinder() {
    }
    
    void addNum(int num) {
        if(maxHeap.size() == 0 || num < maxHeap.top())maxHeap.push(num);
        else minHeap.push(num);
        if(maxHeap.size() - minHeap.size() == 2){
            minHeap.push(maxHeap.top());
            maxHeap.pop();
        }else if(minHeap.size() - maxHeap.size() == 2){
            maxHeap.push(minHeap.top());
            minHeap.pop();
        }
    }
    
    double findMedian() {
        switch(minHeap.size() - maxHeap.size()){
            case 0:return (minHeap.top() + maxHeap.top())/2.0;
            case 1:return minHeap.top();
            case -1:return maxHeap.top();
            default:return -222;
        }
    }
};

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder* obj = new MedianFinder();
 * obj->addNum(num);
 * double param_2 = obj->findMedian();
 */

23. 合并K个排序链表

264. 丑数 II

这两个题目有点类似的感觉，都是由堆顶元素扩展出新的元素入堆，然后判断条件是否满足，

然后第k大的，第k小的，和第n个元素没啥区别，第k大的就是一个递增序列中的第k个而已，

然后是取堆顶元素扩展所有可能的元素这个思路。

或者说丑数序列就可以看出一个三路的链表，当然了说是一棵树更合适。

2 2*2 2 *3 2 * 5 ...

3 3*3 3 * 5 3 * 3 * 3 ...

5 5 * 5 5 * 5 * 5 ...

class Solution {
public:
    struct cmp{
        bool operator()(ListNode*a,ListNode*b){
            return a->val > b->val;
        }
    };
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        priority_queue<ListNode*,vector<ListNode*>,cmp> heap;
        ListNode Vhead(0),*p = &Vhead; 
        for(ListNode *node :lists){
            if(node!=NULL)heap.push(node);
        }
        while(!heap.empty()){
            ListNode * tmp = heap.top();
            heap.pop();
            if(tmp->next!=NULL)heap.push(tmp->next);
            p->next = tmp;
            p = tmp;
        }
        return Vhead.next;
    }
};

ps： 堆维护的是一个不变的一个队列，如果是求随着时间变化的一个集合中的最小值的话，可以寻找相对不变的放到一个堆里，然后在这些堆里寻找最值。