堆的应用.md

堆

堆是一个完全二叉树，其特性为最小或最大节点均在顶部，因此分为最小堆和最大堆。

常用操作	解释
make_heap	将一个数组构造成堆
push	插入一个值进入堆
pop	弹出堆顶元素
top	获得堆顶元素

根据堆完全二叉树堆特性，若当前元素下标为index，那么他的左孩子下标为2*index+1，右孩子下标为2*index+2。他的父亲节点下标为(index-1)/2。在使用时，必须注意这些下标的范围，[0,length-1]。

由于堆的特性，最常用的两个函数，上浮和下沉。上浮常用于在插入一个元素后，把尾端元素按大小关系上浮找到合适的位置。下沉指将一个元素按大小关系向下找到合适的位置。

     5
    / \
   3   6
  / \
 1   2
 在数组中的顺序为 [5,3,6,1,2]，以此构建一个最大堆，最大元素在顶部。

下沉

1. 对元素5下沉，其下标为0，其左右孩子下标为1=2*0+1和2=2*0+2。
2. 在左右孩子中找到较大的值，即为6，交换元素5和元素6，得到

     6
    / \
   3   5
  / \
 1   2
 在数组中的顺序为 [6,3,5,1,2]

3.此时对交换过的孩子进行递归调用，元素5的左右孩子都为空，此时递归调用结束。

上浮

     5
    / \
   3   6
  / \
 1   2
 在数组中的顺序为 [5,3,6,1,2]，以此构建一个最大堆，最大元素在顶部。

1. 对元素6，下标为2进行上浮，如果该元素大于其父亲节点，下标为0=(2-1)/2，则交换，得到，

     6
    / \
   3   5
  / \
 1   2
 在数组中的顺序为 [6,3,5,1,2]

2. 因为交换后6元素已无父亲节点，因此递归结束。

根据这两个基础的操作实现对堆的构造，入堆，出堆等操作。

题目：数据流中的第K大元素，设计一个找到数据流中第K大元素的类（class）。注意是排序后的第K大元素，不是第K个不同的元素。

分析

1. 使用一个堆来存储数据流中K个最大的数，此时应该用最小堆，这是第K大的树刚好在堆顶。
2. 当数据流进入一个数时，当堆未满时，即堆元素个数小于K，将新进入的元素插入到数组尾部，并对该元素上浮。
3. 当堆元素个数大于等于K时，
   1. 如果大于堆顶元素，则替换堆顶元素，并对该堆顶元素进行下沉。
   2. 如果小于堆顶元素，则忽略该元素。

class KthLargest {
public:
    int k_;
    vector<int> heap;

    void up(){
        int index = heap.size() -1 ;
        int parent = (index-1)/2;
        while(parent >= 0){
            if( heap[index] < heap[parent]){
                swap(heap[index],heap[parent]);
            }else{
                break;
            }
            index = parent;
            if(index -1<0){
                break;
            }
            parent = (index-1)/2;
        }
    }

    void down(int u){
        int t = u;
        if( u*2 <= size && h[u*2] < h[t]) t = u *2;
        if(u*2+1<=size && h[u*2+1]<h[t]) t = u*2 + 1;
        if(u != t) { 
            swap(h[u],h[t]);
            down(t);
        }
    }

    void up(int u){
        while(u/2 && h[u/2] > h[u]){
            swap(h[u/2],h[u]);
            u /= 2;
        }
    }

    void down(){
        int index = 0;
        int child = 2*index+1;
        while(child<k_){
            if(child+1<k_ && heap[child+1]<heap[child]){
                child++;
            }
            if(heap[child] < heap[index]){
                swap(heap[child],heap[index]);
            }else{
                break;
            }
            index = child;
            child = 2*index+1;
        }
    }

    void push(int val){
        if(heap.size() < k_){
            heap.push_back(val);
            up();
        }else{
            if(heap[0] < val){
                heap[0] = val;
                down();
            }
        }
    }
    KthLargest(int k, vector<int>& nums) {
        k_ = k;
        for(int i = 0; i < nums.size();i++){
            push(nums[i]);
        }
    }
    
    int add(int val) {
         push(val);
         return heap[0];
    }
};

int quick_sort(vector<int> &nums, int l, int r, int k) {
        if (l>=r) {
            return nums[l];
        }

        int mid = l + r >> 1;
        int i = l -1 , j = r + 1;
        int x = nums[mid];
        while(i<j) {
            while(nums[++i] > x) {}
            while(nums[--j] < x) {}
            if (i < j ) 
                swap(nums[i], nums[j]);
        }
        int sl = j - l + 1;
        if (k <= sl) return quick_sort(nums, l, j, k);

        return quick_sort(nums, j+1, r, k-sl);
        
    }

    int KMax(vector<int>& nums, int k) {
        return quick_sort(nums, 0, nums.size()-1, k);
    }

题目：合并K个链表。合并 k 个排序链表，返回合并后的排序链表。

分析：可以构建一个堆，获取这K个链表当前的最小值，选择最小值进入排序的链表。然后将最小值所在的链表的指针后移，注意指针后移后可能为空，因此需要判断，动态调整堆的大小。

C++代码

class Solution {
public:

    void down(vector<ListNode*> &heap,int index,int length){
        int child = index*2+1;
        while(child<length){
            if(child+1<length && heap[child+1]->val < heap[child]->val){
                child++;
            }
            if(heap[child]->val <heap[index]->val){   //最小堆
                swap(heap[child],heap[index]);
            }else{
                break;
            }
            index = child;
            child = 2*index+1;
        }
    }

    void make_heap(vector<ListNode*> &heap,int length){
        for(int i = length/2;i>=0;i--){
            down(heap,i,length);
        }
    }

    ListNode* mergeKLists(vector<ListNode*>& lists) {
        vector<ListNode*> heap;
        for(auto iter: lists){
            if(iter){
                heap.push_back(iter);
            }
        }
        int length = heap.size();
        make_heap(heap,length);
        ListNode* head = new ListNode(-1);
        //取一个顶点
        ListNode* p = head;
        while(length){
            p->next = heap[0];
            if(heap[0]->next == nullptr){
                swap(heap[0],heap[length-1]);
                length-= 1;
                down(heap,0,length);
            }else{
                heap[0] = heap[0]->next;
                down(heap,0,length);
            }
            p = p->next;
        }
        ListNode* res = head->next;
        delete head;
        return res;
    }
};

class Solution {
public:

    void down(vector<ListNode*> &h, int u) {
        int t = u;
        if (u*2 <= h.size() -1 && h[u*2]->val < h[t]->val ) t = u*2;
        if (u*2+1 <= h.size() -1 && h[u*2+1]->val < h[t]->val ) t = u*2+1;
        if (t != u) {
            swap(h[t], h[u]);
            down(h, t);
        }
    }

    void up(vector<ListNode*> &h, int u) {
        while(u/2 && h[u/2]->val > h[u]->val) {
            swap(h[u/2], h[u]);
            u = u/2;
        }
    }

    ListNode* heapPop(vector<ListNode*> &h) {
        ListNode* ans = h[1];
        h[1] = h[1]->next;
        if (h[1] == nullptr) {
            swap(h[1], h[h.size()-1]);
            h.pop_back();
        }
        down(h, 1);
        return ans;
    }
    void init(vector<ListNode*> &h, vector<ListNode*>& lists) {
        h.push_back(nullptr);
        for (int i = 0; i < lists.size(); i++){
            if (lists[i] == nullptr) continue;
            h.push_back(lists[i]);
        }
        for (int i = (h.size()-1) /2 ; i>=1; i--){
            down(h, i);
        }
    }

    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if (lists.size() == 0) return nullptr;
        
        vector<ListNode*> h;
        init(h, lists);
        ListNode* res = new ListNode(0);
        ListNode* p = res;
        while(h.size() > 1) {
            p->next = heapPop(h);
            p = p->next;
        }
        
        return res->next;
    }
};