Priority Queues

Heap(这下听懂了)

[TOC]

Definition

definition: A max heap(min Heap)

• is A complete binary tree

• The value in each node is greater(less) than or equal to those in its children(if any).

Insertion

先加到最下面,再逐级调整

private static Heap insert(Comparable x){
    int i = ++CurrentSize;
    while(i != 1 && x > heap[i / 2]){
        heap[i] = heap[i / 2];
        i /= 2;
    }
    heap[i] = x;
    return this;
}//这是i = 0位置不放元素的情况 放的话把i / 2改成 (i - 1) / 2即可

Deletion

其实原理也一样,就是把最上面的删了之后,把最下面的放上去,然后调整

public static delete(){
    if(CurrentSize == 0){
        throw OutOfBounds();
    }
    Comparable y = heap[CurrentSize--];
    int i = 1;
 	int ci = 2;
    while(ci <= CurrentSize){
        if(ci < CurrentSize && heap[ci] < heap[ci + 1]){
            ci++;
        }
        if(y.compareTo(heap[ci]) >= 0){
            break;
        }
        heap[i] = heap[ci];
        i = ci;
        ci *= 2;
    }
    heap[i] = y;
    return this;
}

Initialize

private void buildHeap(){
    for(int i = currentSize / 2; i > 0; i--){
        prelocateDown(i);
    }
}
//自顶向下，逐层判断
private void percolateDown( int hole ){
    int child;
    Comparable tmp = array[ hole ];
    for( ; hole *2 <= currentSize; hole = child )
    { child = hole * 2;//左孩子
     if ( child != currentSize && array[ child + 1 ].compareTo( array[ child ] ) < 0 )
         child++;//先找到两个child中最大的那个
     if( array[child ].compareTo( tmp ) < 0 )
         array[ hole ] = array[ child ];
     else
         break;
    }
    array[hole] = tmp;
}
//这个前提是第一个节点存储在i = 1

PercUp

private static void percUp( Comparable [ ] a, int start ){  
    int j = start,  i = j / 2;
    Comparable temp = a [j];
    while (j > 1){ 
        if ( a[i] <= temp) 
            break;
        else {
            a[j] = a[i]; 
            j= i;  
            i = i / 2; 
        }
    }
    a[j] = temp;
}