# 130.Heapify

## 1.Description(Medium)

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**](https://www.lintcode.com/en/problem/heapify/#challenge)

O(n) time complexity

[**Tags**](https://www.lintcode.com/en/problem/heapify/#tags)

[Heap](https://www.lintcode.com/tag/heap/) [LintCode Copyright](https://www.lintcode.com/tag/lintcode-copyright/)

## 2.Code

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

这里值得注意的是，对于扫描整个array的情况下，siftup和siftdown有complexity上的区别。

基本的原因在于：

siftdown的complexity，实质上是node相对于bottom移动的次数，而根据binary heap本身的特性，决定了约靠近bottom的node越多；O(n)

相对照的是siftup，是node相对于root节点的移动次数。O(nlogn)

如果Heapify可以用O(n)实现，那么HeapSort所需的时间复杂度为何是O(nlogn)？因为HeapSort其实包含了两个步骤，第一步，Heapify，build (min) heap，所需时间复杂度O(n)，第二步，依次删除最小值（min heap），对于Heap来说，删除操作的复杂度是O(logn)， 而这个删除需要执行O(n)，来得到最终sort的结果，于是总体时间复杂度是O(nlogn)。

Version 1: Sift Up --O(nlogn)

```
//Version1: SiftUp O(nlogn)
    public void siftup(int[] A,int i){
        while(i!=0){
            int parent=(i-1)/2;
            if(A[parent]<A[i]){
                break;
            }
            int temp=A[parent];
            A[parent]=A[i];
            A[i]=temp;

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

Version 2: Sift Down --O(n)

```
//Version 2:Sift Down O(n)
    public void siftdown(int[] A,int i){
        while(i<A.length){
            int smallest=i;
            if(i*2+1<A.length && A[i*2+1]<A[smallest]){
                smallest=i*2+1;
            }
            if(i*2+2<A.length && A[i*2+2]<A[smallest]){
                smallest=i*2+2;
            }

            if(smallest==i){
                break;
            }

            int temp=A[smallest];
            A[smallest]=A[i];
            A[i]=temp;

            i=smallest;        
        }
    }

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