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

O(n) time complexity

Tags

Heap 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);
        }
    }