package com.snail.basic;
public class MaxPQ<Key extends Comparable<Key>> {
private Key[] pq;
private int N;
public MaxPQ(int Max){
pq = (Key[])new Comparable[Max];
}
// 判断是否为空
public boolean isEmpty(){
return N==0;
}
// 返回队列大小
public int size(){
return N;
}
// 插入
public void insert(Key v){
pq[++N]=v;
swim(N);
}
// 删除最大元素
public Key delMax(){
Key max = pq[1];
exch(1,N--);
pq[N+1]=null;
sink(1);
return max;
}
// 比较
public boolean less(int i, int j){
return pq[i].compareTo(pq[j])>0;
}
// 交换
public void exch(int i, int j){
Key temp = pq[i];
pq[i] = pq[j];
pq[j] = temp;
}
// 由下向上交换
public void swim(int k){
while (k>1 && less(k,k/2)){
exch(k,k/2);
k = k/2;
}
}
// 由上向下交换
public void sink(int k){
while (2*k<=N){
int j = 2*k;
if(j<N && less(j,j+1))j++;
if(!less(k,j))break;
exch(k,j);
k = j;
}
}
}
基于堆的优先队列
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
- 文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
推荐阅读更多精彩内容
- 二叉堆 堆有序定义：当一颗二叉树的每个节点都大于等于它的两个子节点时， 被称为堆有序。二叉堆定义： 二叉堆是一组能...
- 版本记录 前言 将数据结构和算法比作计算机的基石毫不为过，追求程序的高效是每一个软件工程师的梦想。下面就是我对算法...
- 这里实现的优先队列是基于最大堆实现的，java系统是基于最小堆实现的。 队列接口 优先队列实现 LeetCode上...
- 思路 取堆的一半后，分解最小子堆 （使用sink()，如果子结点有比父结点大的值的话 取较大子结点和父结点交换，满...
