130. Heapify

Leave a comment

September 3, 2016 by oneOokay

疑惑了一下Array heapify 成一个max heap和build 一个max tree(https://oneokay.wordpress.com/2016/09/02/126-max-tree/)有什么不同:

  • heapify: 把一个array变成一个heap,是一个complete binary tree。A Complete binary tree is a binary tree in which every node other than the leaves has two children. In complete binary tree at every level, except possibly the last, is completely filled, and all nodes are as far left as possible.  这个人的heap sort post 可以读一下,写的挺好的:heap sort 是一个不断的heapify的过程。http://javabypatel.blogspot.in/2015/11/heap-sort-algorithm.html。以后得补一补heap sort。
  • Max Tree 不一样,不一定是一个complete binary tree.

首先心里要把array想象成一个结构上的complete tree,根据每个i就能知道它的左儿子(2 * i + 1)和右儿子(2 * i + 2). 我们要对每一个这个组<root, left child, right child> (right child可能从缺)进行判断看是否root最小,否则把最小的跟root置换。置换完了之后,再对变动的那个儿子节点进行判断,因为置换可能会影响该儿子节点和他的子节点的大小关系。

从哪里开始进行判断?从 A.length / 2 – 1 开始。因为之后的元素都是叶子节点了,没有判断的必要。

ShiftDOWN O(n) ??? 

public void heapify(int[] A) {
if (A == null || A.length <= 1) {
return;
}

for (int i = A.length / 2 – 1; i >= 0; i –) { //从这里开始,往前进行判断。往后就都是叶子节点了,没必要。
shiftdown(A, i);
}}

private void shiftdown(int[] A, int k) {
while (k < A.length) { //因为如果有置换的发生,都会是把root跟他的子节点对换,所以发生变化大小可能改变的是子节点,子节点的index大于k,所以这里是k < A.length,也是下移。
int min = k;
int leftChild = k * 2 + 1;
int rightChild = k * 2 + 2;
if (leftChild < A.length && A[leftChild] < A[min]) {
min = leftChild;
}
if (rightChild < A.length && A[rightChild] < A[min]) {
min = rightChild;
}
if (min == k) {
break;
}

int tmp = A[k]; //把k与最小的进行置换。
A[k] = A[min];
A[min] = tmp;

k = min;//换完之后,原来的index = min的位置上的元素发生变化了,所以要再次进行判断,于是把min赋给k
}
}

SHIFT UP: O(nlogn) for – loop:n; 那么 while loop 的logn是怎么来的??

public void heapify(int[] A) {
if (A == null || A.length <= 1) {
return;
}

for (int i = 0; i < A.length; i ++) {
shiftup(A, i);
}
}

private void shiftup(int[] A, int k) {
while (k != 0) { //若交换发生,k会逐渐变小,也是上移。
int min = k;
int father = (k – 1) / 2;
if (A[k] > A[father]) {
break;
}
int tmp = A[k];
A[k] = A[father];
A[father] = tmp;

k = father;//置换发生 father发生变化,重新判断
}
}

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: