Chapter 5 Priority Queues

约 556 个字 22 行代码 7 张图片预计阅读时间 2 分钟

Chapter 5¶

Priority Queues

Binary Heap¶

mintree和perfect binary tree的结合
树的思想，数组来部署

Min Tree¶

每个子树的根节点是子树里最小的数

property¶

\(2^h\leq N\leq 2^{h+1}-1\)
height \(h=\lfloor logN\rfloor\)
完全二叉树，铺完一层再铺下一层
然后给每个节点自上而下，从左到右编号 1 - n
对于节点数为 \(N\)的Heap，前 \(\lfloor N/2 \rfloor\)个节点为内部节点，从 \(\lfloor N/2 \rfloor +1\)到 \(N\) 为叶节点

Array Representation¶

任何BST都可以用array来存，但是如果不是perfect，array有很多浪费的空位
BT[n+1]（BT[0] is not used）
parent和children的index关系

\[ parent(i) = \begin{cases} \lfloor i /2\rfloor & \text{if } i\neq1 \\ None & \text{if } i=1 \end{cases} \]

\[ left\_child(i) = \begin{cases} 2i & \text{if } 2i\leq n\\ None & \text{if } 2i>n \end{cases} \]

\[ right\_child(i) = \begin{cases} 2i+1 & \text{if } 2i+1\leq n\\ None & \text{if } 2i+1>n \end{cases} \]

Operations¶

Percolate upPercolate downInsertDeleteMinDecreaseKey(p, \(\Delta\) ,H)Delete(P,H)BuildHeap(H)

记录p处的数据为data，

然后向上寻根比较；

若上面的大，则 H→Elements[p]=H→Elements[p/2];

H→Elements[p/2]=data;

Percolateup(int p,Priority_Queue H){
    int data=H->Elements[p];
    for (;p>0&&H->Element[p/2]>data;p=p/2){
        H->Elements[p]=H->Elements[p/2];
        H->Elements[p/2]=data;
    }
}

在child不越界size的情况下，进行左右child的比较，选择小的child再和parent对比；

Percolatedown(int p,Priority_Queue H){
    int child=2*p;
    int data=H->Elements[p];
    for (;2*p<=H->size;p=child){
        child=2*p;
        if(child!=H->size && H->Elements[child+1]<H->Elements[child]){
            child++;
        }
        if(data>H->Elements[child]){
                H->Elements[p]=H->Elements[child];
                H->Elements[child]=data;
        }
        else break;
    }
}