Heap(堆) 数据结构整理

Posted on | Edited on | In |

又一基础数据结构的整理，知识需要不停的回顾与学习。

（此处的heap指binary heap, 且是最小堆）

性质

structure

complete binary tree

order

根节点的值 <= 叶节点的值

实现

数组实现（完全二叉树的表示方式）

  • 根节点放在A[1] (A[0]不使用)
  • A[x]的子节点为A[2x]以及A[2x + 1]

操作

Insert O(logN)

从最后向上找，找到适合放入插入值的位置放入。

1
2
3
4
5
6
7
8
9
void insert(vector<int> &heap, int val) {
    heap.push_back(val);
    int idx = heap.size() - 1;
    while (idx > 1 && heap[idx / 2] > val) {
        heap[idx] = heap[idx / 2]; // percolate up
        idx /= 2;
    }
    heap[idx] = val;
}

DeleteMin O(logN)

从根节点出发，找到适合放入最后一个元素的位置放入。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int delete_min(vector<int> &heap) {
    int idx = 1;
    int ret = heap[idx];
    int last = heap.back();
    while (2 * idx < heap.size()) {
        int child = 2 * idx;
        if (child < heap.size() - 1 && heap[child + 1] < heap[child])
            child++; // 找到更小的child
        if (last > heap[child])
            heap[idx] = heap[child]; // percolate down
        else
            break; // 找到最后一个元素插入的合适位置！！！
        idx = child;
    }
    heap[idx] = last;
    heap.pop_back();
    return ret;
}

Build

Naive O(NlogN)

做n次插入操作

1
2
for x in arr:
    insert(heap, x)

O(N)

由下向上，依次进行heapify操作。

时间复杂度分析：

  • 对于高度为h的heapify操作：O(h)
  • 每一层高度为h的最多的节点：$\lceil\frac{n}{2^{h + 1}}\rceil$
  • 两者相乘累加
1
2
3
build_heap(heap):
    for i from heap_size / 2 to 1:
        heapify(heap, i)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void percolate_down(vector<int> &heap, int idx) {
    int val = heap[idx];
    while (2 * idx < heap.size()) {
        int child = 2 * idx;
        if (child < heap.size() - 1 && heap[child + 1] < heap[child])
            child++;
        if (val > heap[child])
            heap[idx] = heap[child];
        else
            break;
        idx = child;
    }
    heap[idx] = val;
}
void build_min_heap(vector<int> &heap) {
    for (int i = heap.size() / 2; i > 0; --i) {
        percolate_down(heap, i);
    }
}

Merge

放到一起，build heap…

相关题目

K-th largest element problem

LeetCode 215. Kth Largest Element in an Array

很经典的题目，用heap可以做，也可以用类似快排那样划分的方式做，似乎有更好的表现，因为每次只用考虑一般，是O(N)的时间复杂度。
Heap Method:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
class Solution {
private:
    void makeHeap(vector<int>& heap) {
        for (int i = heap.size() / 2; i > 0; i--) {
            int idx = i;
            int val = heap[idx];
            while (2 * idx < heap.size()) {
                int child = 2 * idx;
                if (child + 1 < heap.size() && heap[child + 1] > heap[child])
                    child++;
                if (val < heap[child])
                    heap[idx] = heap[child];
                else
                    break;
                idx = child;
            }
            heap[idx] = val;
        }
    }
    int deleteMax(vector<int>& heap) {
        int ret = heap[1];
        int idx = 1;
        int last = heap.back();
        while (2 * idx < heap.size()) {
            int child = 2 * idx;
            if (2 * idx + 1 < heap.size() && heap[2 * idx + 1] > heap[2 * idx])
                child++;
            if (last < heap[child])
                heap[idx] = heap[child];
            else break;
            idx = child;
        }
        heap[idx] = last;
        heap.pop_back();
        return ret;
    }
public:
    int findKthLargest(vector<int>& nums, int k) {
        nums.insert(nums.begin(), 0);
        makeHeap(nums);
        int res = 0;
        for (int i = 0; i < k - 1; i++)
            deleteMax(nums);
        return deleteMax(nums);
    }
};

Partition Method:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
private:
    int partition(vector<int>& nums, int left, int right) {
        int pivot = nums[left];
        int l = left + 1, r = right;
        while (l <= r) {
            if (nums[l] < pivot && nums[r] > pivot)
                swap(nums[l++], nums[r--]);
            if (nums[l] >= pivot)
                l++;
            if (nums[r] <= pivot)
                r--;
        }
        swap(nums[left], nums[r]); // 注意与nums[r]交换
        return r;
    }
public:
    int findKthLargest(vector<int>& nums, int k) {
        int left = 0, right = nums.size() - 1;
        while (true) {
            int mid = partition(nums, left, right);
            if (mid == k - 1)
                return nums[mid];
            if (mid < k - 1)
                left = mid + 1;
            else
                right = mid - 1;
        }
    }
};

Top K Frequent

LeetCode 692. Top K Frequent Words

这个题，题目一般，不够经典，但是记下来用于回顾cpp标准库中的priority_queue的使用，包括自己写comparator等。

注意些comparator时判断的符号！！！
记住，默认排序的时候，排升序，默认用小于号比较，其它的基于这个可以推出。
比如这道题，是最大堆，所以应该是”排降序“，用大于号。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    vector<string> topKFrequent(vector<string>& words, int k) {
        unordered_map<string, int> m;
        for (string word : words)
            m[word]++;
        auto comp = [](const pair<string, int>& p1, const pair<string, int>& p2) {
            if (p1.second == p2.second)
                return p1.first > p2.first;
            return p1.second < p2.second;
        };
        vector<string> res;
        priority_queue< pair<string, int>, vector<pair<string, int>>, decltype(comp) > q(comp);
        for (pair<string, int> p : m) {
            q.push(p);
        }
        for (int i = 0; i < k; i++) {
            res.push_back(q.top().first);
            q.pop();
        }
        return res;
    }
};