堆|堆 --- 优先队列问题
1、入队列
把元素插入数组末尾，然后进行向上调整；
2、出队列·
如果数组不为空时，取数组最后一个元素，下标为（size-1），赋值到下标为0的元素上；
尾删最后一个元素，即 size–；
然后将0号下标元素向下调整；
3、取队首元素
如果数组不为空时，取数组下标为0的元素；
【堆|堆 --- 优先队列问题】优先队列实现过程
// 以大堆为例
public class MyPriorityQueue {private int[] array = new int[100];
// 不考虑扩容问题
private int size = 0;
// [0,size) 为数组下标// 入队列 ----数组尾插向上调整
private void offer(int x) {
// 把 x 放到数组的末尾
array[size] = x;
size++;
// 把 x 进行向上调整
// 第一个参数是数组
// 第二个参数是数组大小
// 第三个参数是从哪个位置开始向上调整
shiftUp(array, size, size-1);
}// 出队列 ---- 数组头删向下调整
private Integer poll() {
if(size == 0) {
return null;
}
int ret = array[0];
// 将最后一个元素的值赋值给第下标为0的元素
array[0] = array[size-1];
size--;
// 从 0 号下标位置向下调整
shiftDown(array,size,0);
return ret;
}// 向上调整
private void shiftUp(int[] array, int size,int index) {
int child = index;
int parent = (child - 1)/2;
// 当 child 等于 0 时，就是指向根节点
while(child > 0) {
// 比较当前 child 和 parent 之间的大小关系，看是否符合大堆要求
if(array[child] > array[parent]) {
int tmp = array[child];
array[child] = array[parent];
array[parent] = tmp;
}else {
break;
}
child = parent;
parent = (child - 1)/2;
}
}// 向下调整
private void shiftDown(int[] array, int size, int index) {
int parent = index;
int child = parent*2 + 1;
while (child < size) {
if(child + 1 < size && array[child+1] > array[child]) {
child = child + 1;
}
if(array[child] > array[parent]) {
int tmp = array[child];
array[child] = array[parent];
array[parent] = tmp;
}else {
break;
}
parent = child;
child = 2*parent + 1;
}
}// 取队首元素
private Integer peak() {
if(size == 0) {
return null;
}
return array[0];
}// 判空
private boolean isEmpty() {
return size == 0;
}public static void main(String[] args) {
MyPriorityQueue queue = new MyPriorityQueue();
queue.offer(2);
queue.offer(4);
queue.offer(8);
queue.offer(3);
queue.offer(1);
queue.offer(9);
// 循环出队列
while(!queue.isEmpty()) {
System.out.print(queue.poll()+" ");
}
}
}推荐阅读
- 球松
- Python爬虫|Python爬虫 --- 1.4 正则表达式（re库）
- 振兴中华---争做新时代的好少年
- 青春的恋习曲
- 《将来的你，一定会感谢现在战胜烦恼的自己-------第四章/第十一节/用逆向思维解除烦恼》
- 富裕的好处是对资源的优先占有
- [源码解析]|[源码解析] NVIDIA HugeCTR，GPU版本参数服务器---(3)
- 无私便是最大的自私---多久没有无私过了
- 《教育心理学》读书笔记五---关注特殊群体学生|《教育心理学》读书笔记五---关注特殊群体学生 做有温度的教育
- 【图解】9张图彻底搞懂堆排序