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].
Example
Given [3,2,1,4,5], return [1,2,3,4,5] or any legal heap array.
Challenge
O(n) time complexity
Clarification
What 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.
Solution:
I implemented a Heap class that can specify min heap or max heap with insert, delete root and build heap functions.
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 array 106 * @return: void 107 */ 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 }