Heapify

Question

  1. Given an integer array, heapify it into a min-heap array.
  3. For a heap array A, A[0] is the root of heap, and for each A[i],
  4. A[i * 2 + 1] is the left child of A[i] and A[i * 2 + 2] is the right child of A[i].
  6. Example
  7. Given [3,2,1,4,5], return [1,2,3,4,5] or any legal heap array.
  9. Challenge
  10. O(n) time complexity
  12. Clarification
  13. What is heap?
  15. Heap is a data structure, which usually have three methods: push, pop and top.
  16. where "push" add a new element the heap,
  17. "pop" delete the minimum/maximum element in the heap,
  18. "top" return the minimum/maximum element.
  20. What is heapify?
  21. Convert an unordered integer array into a heap array.
  22. If it is min-heap, for each element A[i],
  23. we will get A[i * 2 + 1] >= A[i] and A[i * 2 + 2] >= A[i].
  25. What if there is a lot of solutions?
  26. Return any of them.

题解

参考前文提到的 Heap Sort 可知此题要实现的只是小根堆的堆化过程，并不要求堆排。

C++

  1. class Solution {
  2. public:
  3.     /**
  4.      * @param A: Given an integer array
  5.      * @return: void
  6.      */
  7.     void heapify(vector<int> &A) {
  8.         // build min heap
  9.         for (int i = A.size() / 2; i >= 0; --i) {
  10.             min_heap(A, i);
  11.         }
  12.     }
  14. private:
  15.     void min_heap(vector<int> &nums, int k) {
  16.         int len = nums.size();
  17.         while (k < len) {
  18.             int min_index = k;
  19.             // left leaf node search
  20.             if (k * 2 + 1 < len && nums[k * 2 + 1] < nums[min_index]) {
  21.                 min_index = k * 2 + 1;
  22.             }
  23.             // right leaf node search
  24.             if (k * 2 + 2 < len && nums[k * 2 + 2] < nums[min_index]) {
  25.                 min_index = k * 2 + 2;
  26.             }
  27.             if (k == min_index) {
  28.                 break;
  29.             }
  30.             // swap with the minimal
  31.             int temp = nums[k];
  32.             nums[k] = nums[min_index];
  33.             nums[min_index] = temp;
  34.             // not only current index
  35.             k = min_index;
  36.         }
  37.     }
  38. };

源码分析

堆排的简化版，最后一步k = min_index不能忘，因为增删节点时需要重新建堆，这样才能保证到第一个节点时数组已经是二叉堆。

复杂度分析

由于采用的是自底向上的建堆方式，时间复杂度为 (N), 证明待补充…

Reference