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 1: For each of the node in the heap array, use siftup method once.
public void heapify(int[] A) {
if (A == null || A.length <= 1) {
return;
}
for (int i = 0; i < A.length; i++) {
siftUp(A, );
}
}
public void siftUp(int[] A, int index) {
int parentIndex = (index - 1) / 2;
while (parentIndex >= 0 && A[index] < A[parentIndex]) {
swap(A, index, parentIndex);
index = parentIndex;
parentIndex = (index - 1) / 2;
}
}
public void swap(int[] A, int a, int b) {
int tmp = A[a];
A[a] = A[b];
A[b] = tmp;
}
Solution 2. for A[0, …, n/2-1] non leaf nodes, call siftDown method, O(n) time complexity.
比solution1时间上更优因为可以节省最下行叶子节点的时间， 叶子节点不需要siftdown.
public void heapify(int[] A) {
if (A == null || A.length <= 1) {
return;
}
for (int i = A.length / 2 - 1; i >= 0; i--) {
siftDown(A, i);
}
}
public void siftDown(int[] A, int index) {
while (index < A.length) {
int smallest = index;
if (index * 2 + 1 < A.length && A[index * 2 + 1] < A[smallest]) {
smallest = index * 2 + 1;
}
if (index * 2 + 2 < A.length && A[index * 2 + 2] < A[smallest]) {
smallest = index * 2 + 2;
}
if (smallest == index) {
break;
}
swap(A, smallest, index);
index = smallest;
}
}
public void swap(int[] A, int a, int b) {
int tmp = A[a];
A[a] = A[b];
A[b] = tmp;
}
