二叉堆的特性（基于二叉树结构）
- 最大堆的堆顶是整个堆中的最大元素
- 最小堆的堆顶是整个堆中的最小元素
二叉堆的的插入和删除（包含堆的重建）时间复杂度都是O（logn），构建是O（n）
下面是图解（借用了图片）
1.插入过程
第一步：
image.png
第二步：
image.png
第三步：
image.png
2.删除过程
第一步：
image.png
第二步：
image.png
第三步：
image.png
第四步：
image.png
第五步：
image.png
第六步：
image.png
以下为代码实现
public class BinaryHeap {
// 上浮
public static void upAdjust(int[] array) {
// 找出最后一个节点
int childIndex = array.length - 1;
// 先拿出需要上浮节点的值
int temp = array[childIndex];
// 根据推算找出节点的父节点
int parentIndex = (childIndex - 1) / 2;
while (childIndex > 0 && array[parentIndex] > temp) {
// 如果父节点值大于子节点，则进行交换
array[childIndex] = array[parentIndex];
childIndex = parentIndex;
parentIndex = (childIndex - 1) / 2;
}
array[parentIndex] = temp;
}
public static void downAdjust(int[] array, int parentIndex, int length) {
// 先拿出父节点的值
int parentData = array[parentIndex];
// 得到左子节点的位置
int childIndex = 2 * parentIndex + 1;
// 当子节点的下标已经超出数组下标，跳出循环
while (childIndex < length) {
// 定位左子节点和右子节点的大小
if (childIndex + 1 < array.length && array[childIndex + 1] < array[childIndex]) {
childIndex++;
}
// 如果父节点小于任何一个子节点则跳出
if (parentData < array[childIndex]) {
return;
}
// 将子节点上浮，然后下标进行下浮
array[parentIndex] = array[childIndex];
parentIndex = childIndex;
childIndex = 2 * parentIndex + 1;
}
// 最后跳出循环的点，是父节点已经不存在子节点了，已经遍历到根节点，进行赋值
array[parentIndex] = parentData;
}
public static void main(String[] args) {
int[] array = new int[] {1, 3, 2, 6, 5, 7, 8, 9, 10, 0};
upAdjust(array);
System.out.println(Arrays.toString(array));
array = new int[] {7, 1, 3, 10, 5, 2, 8, 9, 6};
buildHeap(array);
System.out.println(Arrays.toString(array));
}
private static void buildHeap(int[] array) {
// 构造二叉堆
for (int i = (array.length - 2) / 2; i >= 0; i--) {
downAdjust(array, i, array.length);
}
}
public class PriorityQueue {
int[] array = new int[10];
int size;
public void enQueue(int data) {
if (size == array.length) {
resize();
}
// 放到最后一个位置
array[size++] = data;
upAdjust();
}
private void upAdjust() {
int childIndex = size - 1;
int childData = array[childIndex];
int parentIndex = (childIndex - 1) / 2;
while (childIndex > 0 && array[parentIndex] < childData) {
array[childIndex] = array[parentIndex];
childIndex = parentIndex;
parentIndex = (childIndex - 1) / 2;
}
array[childIndex] = childData;
}
private int deQueue() {
if (size == 0) {
throw new IndexOutOfBoundsException("队列为空");
}
int waitPopData = array[0];
array[0] = array[--size];
downAdjust();
return waitPopData;
}
private void downAdjust() {
int parentIndex = 0;
int childIndex = 1;
int temp = array[parentIndex];
while (childIndex < size) {
if (childIndex + 1 < size && array[childIndex + 1] > array[childIndex]) {
childIndex++;
}
if (temp >= array[childIndex]) {
break;
}
array[parentIndex] = array[childIndex];
parentIndex = childIndex;
childIndex = 2 * parentIndex + 1;
}
array[parentIndex] = temp;
}
private void resize() {
array = Arrays.copyOf(array, array.length*2);
}
public static void main(String[] args) {
PriorityQueue priorityQueue = new PriorityQueue();
priorityQueue.enQueue(3);
priorityQueue.enQueue(5);
priorityQueue.enQueue(5);
priorityQueue.enQueue(10);
priorityQueue.enQueue(2);
priorityQueue.enQueue(2);
priorityQueue.enQueue(7);
priorityQueue.enQueue(7);
priorityQueue.enQueue(1);
priorityQueue.enQueue(1);
priorityQueue.enQueue(8);
priorityQueue.enQueue(4);
priorityQueue.enQueue(4);
System.out.println("出队元素" + priorityQueue.deQueue());
System.out.println("出队元素" + priorityQueue.deQueue());
System.out.println("出队元素" + priorityQueue.deQueue());
System.out.println("出队元素" + priorityQueue.deQueue());
System.out.println("出队元素" + priorityQueue.deQueue());
System.out.println("出队元素" + priorityQueue.deQueue());
System.out.println("出队元素" + priorityQueue.deQueue());
System.out.println("出队元素" + priorityQueue.deQueue());
System.out.println("出队元素" + priorityQueue.deQueue());
}
}
