# Heapify

Description

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].

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.

Example

Given [3,2,1,4,5], return [1,2,3,4,5] or any legal heap array.

Challenge

O(n) time complexity

## Analysis

Heapify一个Array，也就是对array中的元素进行siftup或者siftdown的操作。根据min heap定义进行操作即可。

The number of operations required for each operation is proportional to the distance the node may have to move. For siftDown, it is the distance from the bottom of the tree, so siftDown is expensive for nodes at the top of the tree. With siftUp, the work is proportional to the distance from the top of the tree, so siftUp is expensive for nodes at the bottom of the tree. Although both operations are O(log n) in the worst case, in a heap, only one node is at the top whereas half the nodes lie in the bottom layer. So it shouldn't be too surprising that if we have to apply an operation to every node, we would prefer siftDown over siftUp

http://stackoverflow.com/questions/9755721/how-can-building-a-heap-be-on-time-complexity

## Solution

#### Sift-up - Time O(nlogn)

``````public class Solution {
/**
* @param A: Given an integer array
* @return: void
*/

private void swap(int[] A, int i, int j) {
int temp = A[i];
A[i] = A[j];
A[j] = temp;
}

private void siftup(int[] A, int k) {
while (k != 0) {
int parent = (k - 1) / 2;
if (A[k] > A[parent]) {
break;
}
swap(A, k, parent);
k = parent;
}
}

public void heapify(int[] A) {
for (int i = 0; i < A.length; i++) {
siftup(A, i);
}
}
}
``````

#### Sift-down - Time O(n)

``````public class Solution {
/**
* @param A: Given an integer array
* @return: void
*/
private void siftdown(int[] A, int k) {
while (k < A.length) {
int smallest = k;
if (k * 2 + 1 < A.length && A[k * 2 + 1] < A[smallest]) {
smallest = k * 2 + 1;
}
if (k * 2 + 2 < A.length && A[k * 2 + 2] < A[smallest]) {
smallest = k * 2 + 2;
}
if (smallest == k) {
break;
}
int temp = A[smallest];
A[smallest] = A[k];
A[k] = temp;

k = smallest;
}
}

public void heapify(int[] A) {
for (int i = A.length / 2; i >= 0; i--) {
siftdown(A, i);
}
}
}
``````