树结构算法总结(4) 堆Heap

Posted by SkyHigh on October 5, 2016

Previous

树结构算法总结(1) 二叉树的遍历
树结构算法总结(2) 线段树Segment Tree
树结构算法总结(3) 字典树Trie Tree

树结构算法总结(4) 堆Heap

堆的概念和建立

概念

我们这里说的堆和内存机制里的堆(内存机制的堆更偏向于链表结构)不一样。数据结构的堆其实是一种排序的完全二叉树(不一定是满二叉树)。对每个节点,它的孩子节点都比它大(最小堆),且堆顶元素是最小值;或者都比它小(最大堆),且堆顶元素是最大值。因此我们可以通过堆来做如下事情:

  • 排序
  • 查找第k个大的数
  • 其他

以下引用自lintcode的简单说明:

什么是堆?

	堆是一种数据结构,它通常有三种方法:push, pop 和 top。其中,“push”添加新的元素进入堆,“pop”删除堆中最小/最大元素,“top”返回堆中最小/最大元素。
什么是堆化?

	把一个无序整数数组变成一个堆数组。如果是最小堆,每个元素A[i],我们将得到A[i * 2 + 1] >= A[i]和A[i * 2 + 2] >= A[i]

如果有很多种堆化的结果?

	返回其中任何一个。

堆化

时间复杂度:O(n)

思路

自下向上对树进行堆排序。当某个节点调整过(比如左孩子和父节点交换,或者右孩子和父节点交换),则需要对该节点(左孩子或右孩子)为根节点的子树进行重新堆排序。

实现
  # 最大堆
class Solution {
public:
    /**
     * @param A: Given an integer array
     * @return: void
     */
    void heapify(vector<int> &A) {
        // write your code here
        heap(A, A.size()-1);
    }
    void heap(vector<int>& A, int m){
        for(int i=m/2;i>=0;i--){
            int cur = 2*i+1;
            while(cur<A.size()){
                if(cur+1<A.size()&&A[cur]<A[cur+1])
                    cur++;
                if(A[cur]>A[(cur-1)/2]){
                    swap(A[cur], A[(cur-1)/2]);
                    cur = 2*cur+1;
                }
                else
                    break;
            }
        }
    }
};

  # 最小堆
class Solution {
public:
    /**
     * @param A: Given an integer array
     * @return: void
     */
    void heapify(vector<int> &A) {
        // write your code here
        heap(A, A.size()-1);
    }
    void heap(vector<int>& A, int m){
        for(int i=m/2;i>=0;i--){
            int cur = 2*i+1;
            while(cur<A.size()){
                if(cur+1<A.size()&&A[cur]>A[cur+1])
                    cur++;
                if(A[cur]<A[(cur-1)/2]){
                    swap(A[cur], A[(cur-1)/2]);
                    cur = 2*cur+1;
                }
                else
                    break;
            }
        }
    }
};

堆的应用

排序矩阵中的从小到大第k个数

在一个排序矩阵中找从小到大的第 k 个整数。

排序矩阵的定义为:每一行递增,每一列也递增。

给出 k = 4 和一个排序矩阵:

[
  [1 ,5 ,7],
  [3 ,7 ,8],
  [4 ,8 ,9],
]

返回 5。
思路

考虑第k个,且矩阵排序,则这个元素一定在(i+1)*(j+1)范围里,因此缩小了遍历空间。之后将每个元素存入优先队列(下面有说明)中,且保持优先队列中的元素个数为k个,一旦有比优先队列中最大值小的元素,则将该元素放入队列中,并pop出最大值元素。这样最后只要输出优先队列的最大值即为从小到大第k个数。

实现
class Solution {
public:
    /**
     * @param matrix: a matrix of integers
     * @param k: an integer
     * @return: the kth smallest number in the matrix
     */
     struct comp{
         bool operator() (int a, int b){
             return a<b;
         }
     };
    int kthSmallest(vector<vector<int> > &matrix, int k) {
        // write your code here
        priority_queue<int, vector<int>, comp> pq;
        int m = matrix.size();
        if(m<1)
            return 0;
        int n = matrix[0].size();
        for(int i=0;i<m;i++){
            for(int j=0;j<n&&(i+1)*(j+1)<=k;j++){
                if(pq.size()<k)
                    pq.push(matrix[i][j]);
                else{
                    if(pq.top()>matrix[i][j]){
                        pq.pop();
                        pq.push(matrix[i][j]);
                    }
                    else
                        break;
                }
            }
        }
        return pq.top();
    }
};
说明

priority_queue是C++里一种优先队列的数据结构。它的模板定义如下:

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

上面的T,对应题目的int,表示存储的元素为int;上面的Container,对应题目的vector,表示存储元素的容器;上面的Compare类,对应题目的comp类,表示比较器。

比较器的说明:
priority_queue默认使用最大堆的方式,对应的比较器为less(即a<b),最大的元素排在队列前面。当使用pq.top()时,访问的是队列头元素。
比较器是用于比较两个元素的大小或其它性质的逻辑判断,用于队列里的元素排序。

具体可以参考:cplusplus.priority_queue

合并k个排序链表

合并k个排序链表,并且返回合并后的排序链表。尝试分析和描述其复杂度。

给出3个排序链表[2->4->null,null,-1->null],返回 -1->2->4->null

思路

先把所有的链表元素进行堆排序,之后直接输出每个元素,并把它们串起来。

实现
/**
 * Definition of ListNode
 * class ListNode {
 * public:
 *     int val;
 *     ListNode *next;
 *     ListNode(int val) {
 *         this->val = val;
 *         this->next = NULL;
 *     }
 * }
 */
class Solution {
public:
    /**
     * @param lists: a list of ListNode
     * @return: The head of one sorted list.
     */
    ListNode *mergeKLists(vector<ListNode *> &lists) {
        // write your code here
        vector<ListNode *> res;
        for(auto link:lists){
            while(link){
                res.push_back(link);
                link = link->next;
            }
        }
        if(res.empty())
            return NULL;
        auto f = [](ListNode* a, ListNode* b){return a->val>b->val;};
        make_heap(res.begin(), res.end(), f);
        ListNode* head = res[0];
        pop_heap(res.begin(), res.end(), f);
        res.pop_back();
        ListNode* h = head;
        while(!res.empty()){
            head->next = res[0];
            pop_heap(res.begin(), res.end(), f);
            res.pop_back();
            head = head->next;
        }
        return h;
    }
};
说明
  • auto f = [](ListNode* a, ListNode* b){return a->val>b->val;};对应的是比较器,只不过这里我们使用函数指针来代替。

  • make_heappush_heappop_heapsort_heap都是默认按最大堆排序。
    • make_heap:进行堆化(最大元素在开头);
    • push_heap:如果有新元素加入,则需要使用push_heap(一般要先push元素,再用该命令);
    • pop_heap:如果要删除元素,则使用该命令(一般先用该命令,再pop掉元素);
    • sort_heap:直接进行堆排序,默认为从小到大;
    • 操作后三个命令之前,必须要进行一次make_heap(初始化的时候用就可以了)。
  • 上面四个命令和priority_queue(大致)等价。
  • 具体参考:make_heap