Given an integer array, heapify it into a min-heap array.For a heap array A, A[0] is the root of heap, and for each A[i], A[i * 2 + 1] is the left child of A[i] and A[i * 2 + 2] is the right child of A[i].ExampleGiven [3,2,1,4,5], return [1,2,3,4,5] or any legal heap array.ChallengeO(n) time complexityClarificationWhat is heap?Heap is a data structure, which usually have three methods: push, pop and top. where "push" add a new element the heap, "pop" delete the minimum/maximum element in the heap, "top" return the minimum/maximum element.What is heapify?Convert an unordered integer array into a heap array. If it is min-heap, for each element A[i], we will get A[i * 2 + 1] >= A[i] and A[i * 2 + 2] >= A[i].What if there is a lot of solutions?Return any of them.

Heap的介紹1，介紹2，要注意complete tree和full tree的區別, Heap是complete tree；Heap里面 i 的 children分別是 i*2+1 和 i*2+2，i 的 parent是 　(i-1)/2

Heapify的基本思路就是：Given an array of N values, a heap containing those values can be built by simply “sifting” each internal node down to its PRoper location：

1.start with the last internal node

2.swap the current internal node with its smaller child, if necessary

3.then follow the swapped node down

4.continue until all internal nodes are done

 1 public class Solution { 2     /** 3      * @param A: Given an integer array 4      * @return: void 5      */ 6     public void heapify(int[] A) { 7         int start = A.length/2; 8         for (int i=start;i>=0;i--) 9             shiftDown(i, A);10     }11     12     private void shiftDown(int ind, int[] A){13         int size = A.length;14         int left = ind*2+1;15         int right = ind*2+2;16         while (left<size || right<size){17             int leftVal = (left<size) ? A[left] : Integer.MAX_VALUE;18             int rightVal = (right<size) ? A[right] : Integer.MAX_VALUE;19             int next = (leftVal<=rightVal) ? left : right;20             if (A[ind]<A[next]) break;21             else {22                 swap(A, ind,next);23                 ind = next;24                 left = ind*2+1;25                 right = ind*2+2;26             }27         }28     }29     30     private void swap(int[] A, int x, int y){31         int temp = A[x];32         A[x] = A[y];33         A[y] = temp;34     }35 }

注意第7行，start之所以從A.length/2開始，是因為要從Internal node開始，除開最后一行。其實可以寫成start = (A.length - 1 - 1) / 2, 求最后一個index的parent index的基本做法。

17-18行的技巧，不存在就補齊一個很大的數，因為反正最終是求小的，這樣省了很多行分情況討論

下面給出Heap的 Summary, 轉來的：implemented a Heap class that can specify min heap or max heap with insert, delete root and build heap functions.

Time Complexity分析：Binary Heap

Insert: O(logN), Delete: O(logN), Search: O(N), Space: O(N), Build本來應該O(NlogN), 但是如果用巧妙辦法：The optimal method starts by arbitrarily putting the elements on a binary tree, respecting the shape property (the tree could be represented by an array, see below). Then starting from the lowest level and moving upwards, shift the root of each subtree downward as in the deletion algorithm until the heap property is restored. 時間復雜度是 O(N)., 參看上面鏈接里面build a Heap部分證明

  1 class Heap{  2     private int[] nodes;  3     private int size;  4     private boolean isMaxHeap;  5       6     public Heap(int capa, boolean isMax){  7         nodes = new int[capa];  8         size = 0;  9         isMaxHeap = isMax; 10     } 11  12     //Build heap from given array. 13     public Heap(int[] A, boolean isMax){ 14         nodes = new int[A.length]; 15         size = A.length; 16         isMaxHeap = isMax; 17         for (int i=0;i<A.length;i++) nodes[i] = A[i]; 18         int start = A.length/2; 19         for (int i=start;i>=0;i--) 20             shiftDown(i); 21     } 22  23     //Assume A and nodes have the same length. 24     public void getNodesValue(int[] A){ 25         for (int i=0;i<nodes.length;i++) A[i] = nodes[i]; 26     }     27      28     public boolean isEmpty(){ 29         if (size==0) return true; 30         else return false; 31     } 32  33     public int getHeapRootValue(){ 34         //should throw exception when size==0; 35         return nodes[0]; 36     } 37  38     private void swap(int x, int y){ 39         int temp = nodes[x]; 40         nodes[x] = nodes[y]; 41         nodes[y] = temp; 42     } 43  44     public boolean insert(int val){ 45         if (size==nodes.length) return false; 46         size++; 47         nodes[size-1]=val; 48         //check its father iteratively. 49         int cur = size-1; 50         int father = (cur-1)/2; 51         while (father>=0 && ((isMaxHeap && nodes[cur]>nodes[father]) || (!isMaxHeap && nodes[cur]<nodes[father]))){ 52             swap(cur,father); 53             cur = father; 54             father = (cur-1)/2; 55         } 56         return true; 57     } 58  59     private void shiftDown(int ind){ 60         int left = (ind+1)*2-1; 61         int right = (ind+1)*2; 62         while (left<size || right<size){ 63             if (isMaxHeap){ 64                 int leftVal = (left<size) ? nodes[left] : Integer.MIN_VALUE; 65                 int rightVal = (right<size) ? nodes[right] : Integer.MIN_VALUE; 66                 int next = (leftVal>=rightVal) ? left : right; 67                 if (nodes[ind]>nodes[next]) break; 68                 else { 69                     swap(ind,next); 70                     ind = next; 71                     left = (ind+1)*2-1; 72                     right = (ind+1)*2; 73                 } 74             } else { 75                 int leftVal = (left<size) ? nodes[left] : Integer.MAX_VALUE; 76                 int rightVal = (right<size) ? nodes[right] : Integer.MAX_VALUE; 77                 int next = (leftVal<=rightVal) ? left : right; 78                 if (nodes[ind]<nodes[next]) break; 79                 else { 80                     swap(ind,next); 81                     ind = next; 82                     left = (ind+1)*2-1; 83                     right = (ind+1)*2; 84                 } 85             } 86         } 87     }     88  89     public int popHeapRoot(){ 90         //should throw exception, when heap is empty. 91  92         int rootVal = nodes[0]; 93         swap(0,size-1); 94         size--; 95         if (size>0) shiftDown(0); 96         return rootVal; 97     } 98 } 99         100             101     102 103 public class Solution {104     /**105      * @param A: Given an integer array106      * @return: void107      */108     public void heapify(int[] A) {109         if (A.length==0) return;110     111         Heap minHeap = new Heap(A,false);112         minHeap.getNodesValue(A);113     }114 }

經常有關Heap的問題比如：

k largest(or smallest) elements in an arrayWrite an efficient program for printing k largest elements in an array. Elements in array can be in any order.

常用的方法肯定有QuickSelect, 用Heap也有兩種方法可解：

Method Use Max Heap1) Build a Max Heap tree in O(n)2) UseExtract Maxk times to get k maximum elements from the Max Heap O(klogn)

這個Max Heap的size是O（N）

Time complexity: O(n + klogn)

推薦方法:

Method Use Min Heap

1) Build a Min Heap MH of the first k elements (arr[0] to arr[k-1]) of the given array. O(k)

2) For each element, after the kth element (arr[k] to arr[n-1]), compare it with root of MH.　　a) If the element is greater than the root then make it root and callheapifyfor MH　　b) Else ignore it.// The step 2 is O((n-k)*logk)

3) Finally, MH has k largest elements and root of the MH is the kth largest element.

這個Min Heap的size是O（k）

Time Complexity: O(k + (n-k)Logk) without sorted output.