优先级队列(堆)
目录
优先级队列
堆的概念
堆的创建
堆的向下调整
堆的插入
完整代码
优先级队列
队列是一种先进先出的数据结构，有些时候操作的数据可能带有优先级，出队列时就需要优先级高的数据先出队列。
在这种情况下，数据结构应该提供两个最基本的操作，一个是返回最高优先级对象，一个是添加新的对象。这种数 据结构就是优先级队列(Priority Queue)。
堆的概念
如果有一个关键码的集合K = {k0，k1， k2，…，kn-1}，把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中，并满足：Ki = K2i+1 且 Ki >= K2i+2) i = 0，1，2…，则称为小堆(或大堆)。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。
注意：
- 已知孩子节点为i，则双亲节点为 (i-1)/2；
- 已知双亲节点为i，左孩子：2*i+1；右孩子：2*i+2。
堆的创建
堆的向下调整
这里以大根堆为例来讲解堆的向下调整。
题目：对于集合{ 27,15,19,18,28,34,65,49,25,37 }中的数据，如果将其创建成大根堆呢？
首先我们要定义基本变量，来供使用。因为是对于集合中的数据进行创建大根堆，所以我们可以使用数组来进行。
public class TestHeap {
public int[] elem;
public int usedSize;
public TestHeap(){
this.elem = new int[10];
}
}对于如何把数组中的数据放到实现堆的数组里，我们可以通过for循环来进行放置。
注意：这里是有两个数组。
public void intelem(int[] array){
for (int i = 0; i < array.length; i++) {
this.elem[i] = array[i];
usedSize++;
}
}接着我们就要开始创建堆了
public void createHeap(){
for (int parent = (this.usedSize-1-1)/2; parent >= 0 ; parent--) {
shifDown(parent, this.usedSize);//每棵树结束时候都给个10，如果接着调整的节点比10
//大了，说明这棵树一定调整完了
}
}主要的重心在于如何写出shifDown这个方法。
思路：
- 由上面我们能知道 child = parent*2+1。为了确保child的数组不越界，我们要确定循环条件。
- 因为是创建大根堆，所以要找到左右子树的最大值同根节点进行比较、交换。
- 关于break，这里因为当 前一个节点已经结束了，下面的节点也是结束的状态。
/**
*
* @param parent 每棵子树调整的起始位置
* @param usedSize 判断 每棵子树 什么时候 调整结束
*/
private void shifDown(int parent, int usedSize) {
int child = 2*parent+1;
while(child < usedSize){
//找到左右子树的最大值
if(child+1 < usedSize && elem[child] < elem[child+1]){
child++;
}
if(elem[child] > elem[parent]){
swap(elem,child,parent);
parent = child;
child = 2*parent+1;
}else{
break;
}
}
}
private void swap(int[] elem, int i ,int j){
int tmp = elem[i];
elem[i] = elem[j];
elem[j] = tmp;
}通过Test测试类和调试，我们能看到大根堆创建成功了。
public class Test {
public static void main(String[] args) {
int[] array = {27,15,19,18,28,34,65,49,25,37};
TestHeap testHeap = new TestHeap();
//把array的值赋值给testHeap
testHeap.intelem(array);
testHeap.createHeap();
}
创建的堆下图，大根堆。
堆的插入
堆的插入总共需要两个步骤：
- 先将元素放入到底层空间中(注意：空间不够时需要扩容)
- 将最后新插入的节点向上调整，直到满足堆的性质
其实这和上面的创建大根堆有些类似，但这里用到的是向上调整。
//插入
public void push(int val){
if(isFull()){
elem = Arrays.copyOf(elem,2*elem.length);
}
elem[usedSize] = val;
sitUp(usedSize);
usedSize++;
}
public boolean isFull(){
return elem.length == usedSize;
}
}
这里的关键在于向上调整部分代码的编写。
private void sitUp(int child) {
int parent = (child-1)/2;
while(parent >= 0){
if (elem[parent] < elem[child]){
swap(elem,child,parent);
child = parent;
parent = (child-1)/2;
}else{
break;
}
}
}向上调整我们可以先确定孩子节点，最后一棵树的节点位置可以通过 useSize来确定，进而能确定双亲节点。
完整代码
TestHeap类
import java.util.Arrays;
public class TestHeap {
public int[] elem;
public int usedSize;
public TestHeap(){
this.elem = new int[10];
}
public void intelem(int[] array){
for (int i = 0; i < array.length; i++) {
this.elem[i] = array[i];
usedSize++;
}
}
public void createHeap(){
for (int parent = (this.usedSize-1-1)/2; parent >= 0 ; parent--) {
shifDown(parent, this.usedSize);//没棵树结束时候都给个10，如果接着调整的节点比10大了。说明这棵树一定调整完了
}
}
//alt+p+enter 直接生成
/**
*
* @param parent 每棵子树调整的起始位置
* @param usedSize 判断 每棵子树 什么时候 调整结束
*/
private void shifDown(int parent, int usedSize) {
int child = 2*parent+1;
while(child < usedSize){
//找到左右子树的最大值
if(child+1 < usedSize && elem[child] < elem[child+1]){
child++;
}
if(elem[child] > elem[parent]){
swap(elem,child,parent);
parent = child;
child = 2*parent+1;
}else{
break;
}
}
}
//插入
public void push(int val){
if(isFull()){
elem = Arrays.copyOf(elem,2*elem.length);
}
elem[usedSize] = val;
sitUp(usedSize);
usedSize++;
}
private void swap(int[] elem, int i ,int j){
int tmp = elem[i];
elem[i] = elem[j];
elem[j] = tmp;
}
private void sitUp(int child) {
int parent = (child-1)/2;
while(parent >= 0){
if (elem[parent] < elem[child]){
swap(elem,child,parent);
child = parent;
parent = (child-1)/2;
}else{
break;
}
}
}
public boolean isFull(){
return elem.length == usedSize;
}
}Test类
public class Test {
public static void main(String[] args) {
int[] array = {27,15,19,18,28,34,65,49,25,37};
TestHeap testHeap = new TestHeap();
//把array的值赋值给testHeap
testHeap.intelem(array);
testHeap.createHeap();
/*for (int i = 0; i < array.length; i++) {
testHeap.push(array[i]);
}
testHeap.push(80);*/
}
}