Build Min Heap Using Array

本文主要是介绍Build Min Heap Using Array，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Build min-heap using Array.

思路1：首先明白heap的底层implementation就是array，从0开始的parent和left，right的关系为，

如果现在的node index为i，那么parent index就是 (i-1)/2;   left  为2*i+1， right为 2*i+2；

         ( i-1 ) / 2

             i

    2*i+1      2*i+2

记住以上关系图，就可以明白heap的index之间的关系了。

那么build up min heap，有两种方法，一种方法是nlogn的，就是不停的加进去，然后往上swap，把父节点大的点往下挪，小的node往上移动，一直移动到头部(也就是根部)。每次swap是lgn的复杂度，然后总共是nlgn的复杂度。

public class Solution {/** @param A: Given an integer array* @return: nothing*/public void heapify(int[] A) {if(A == null || A.length == 0) {return;}//注意顺序是每扫描一个数，这个数往上移动；i从0开始；for(int i = 0; i < A.length; i++) { siftup(A, i);}}private void siftup(int[] A, int k) {while(k != 0) {int father = (k - 1)/2;if(A[father] > A[k]) {swap(A, father, k);}k = father;}}private void swap(int[] A, int i, int j) {int temp = A[i];A[i] = A[j];A[j] = temp;}
}

思路2，就是一半的array元素不动，倒数第二层总共会有n/2往下移动1层，+ 倒数第三层总共会有n/4的node往下移动2层，以此类推 到最高层 n/2^h，只有1个元素移动h层，最后计算出来是个o(n)的复杂度。也就是只用移动一半的node，往下移动就可以了，总共的步数是O(n)的数量级。https://www.youtube.com/watch?v=MiyLo8adrWw

public class Solution {/** @param A: Given an integer array* @return: nothing*/public void heapify(int[] A) {if(A == null || A.length == 0) {return;}for(int i = A.length / 2; i >= 0; i--) {siftDown(A, i);}}private void siftDown(int[] A, int k) {int smallest = k;while(k < A.length) {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(k == smallest) {break;}swap(A, smallest, k);k = smallest;}}private void swap(int[] A, int i, int j) {int temp = A[i];A[i] = A[j];A[j] = temp;}
}

 

这篇关于Build Min Heap Using Array的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---