一、优先队列和二叉堆
⼆叉堆是⼀种特殊的⼆叉树(完全⼆叉树),因为是完全二叉树,所以存储在数组⾥。
⼀般的链表⼆叉树,我们操作节点的指针,⽽在数组⾥,我们把数组索引作为指针。

注意数组的第⼀个索引 0 空着不⽤,因为这样就可以:
left = root * 2 right = root * 2 + 1
root = left / 2 root = right /2
优先队列就是用二叉堆实现的。优先队列的最大特点就是,当插⼊或者删除元素的时候,队内元素会⾃动排序。这用⼆叉堆很容易实现,且效率为log(n)
。
二、实现 swim 和 sink
对于最⼤堆,会破坏堆性质的有有两种情况:
-
如果某个节点 A ⽐它的⼦节点(中的⼀个)⼩,那么 A 就不配做⽗节 点,应该下去,下⾯那个更⼤的节点上来做⽗节点,这就是对 A 进⾏下沉。
-
如果某个节点 A ⽐它的⽗节点⼤,那么 A 不应该做⼦节点,应该把⽗ 节点换下来,⾃⼰去做⽗节点,这就是对 A 的上浮。
三、实现 push 和 pop
-
insert⽅法先把要插⼊的元素添加到堆底的最后,然后让其上浮到正确位置。
-
pop⽅法先把堆顶元素 A 和堆底最后的元素 B 对调,然后删除 A,最 后让 B 下沉到正确位置。
class priority_queue{
int data[MAX_NUM]; // 存储元素的数组
int count = 0; // 当前队列中的元素个数
public:
bool empty(){
return count == 0;
}
int top(){
if (!empty()) {
return data[1];
}
return -1;
}
void push(int key){
count++;
data[count] = key;
swim(count);
}
void pop(){
exch(1, count);
data[count] = -1;
count--;
sink(1);
}
/* 上浮第k个元素 */
void swim(int k){
while (k>1 && less(parent(k), k)) {
exch(parent(k), k);
k = parent(k);
}
}
/* 下沉第k个元素 */
void sink(int k){
while (left(k) <= count) {
int older = left(k);
if (right(k) <= count && less(older, right(k))) {
older = right(k);
}
if (less(older, k)) break;
exch(k, older);
k = older;
}
}
int parent(int root){
return root/2;
}
int left(int root){
return root * 2;
}
int right(int root){
return root*2 + 1;
}
/* data[i] 是否⽐ data[j] ⼩? */
bool less(int i, int j){
return data[i] < data[j];
}
/* 交换数组的两个元素 */
void exch(int i, int j){
int temp = data[i];
data[i] = data[j];
data[j] = temp;
}
};
网友评论