二叉堆的特性（基于二叉樹結(jié)構(gòu)）
- 最大堆的堆頂是整個(gè)堆中的最大元素
- 最小堆的堆頂是整個(gè)堆中的最小元素
二叉堆的的插入和刪除（包含堆的重建）時(shí)間復(fù)雜度都是O（logn）蜈垮，構(gòu)建是O（n）
下面是圖解（借用了圖片）
1.插入過程
第一步：
image.png
第二步：
image.png
第三步：
image.png
2.刪除過程
第一步：
image.png
第二步：
image.png
第三步：
image.png
第四步：
image.png
第五步：
image.png
第六步：
image.png
以下為代碼實(shí)現(xiàn)
public class BinaryHeap {
// 上浮
public static void upAdjust(int[] array) {
// 找出最后一個(gè)節(jié)點(diǎn)
int childIndex = array.length - 1;
// 先拿出需要上浮節(jié)點(diǎn)的值
int temp = array[childIndex];
// 根據(jù)推算找出節(jié)點(diǎn)的父節(jié)點(diǎn)
int parentIndex = (childIndex - 1) / 2;
while (childIndex > 0 && array[parentIndex] > temp) {
// 如果父節(jié)點(diǎn)值大于子節(jié)點(diǎn)，則進(jìn)行交換
array[childIndex] = array[parentIndex];
childIndex = parentIndex;
parentIndex = (childIndex - 1) / 2;
}
array[parentIndex] = temp;
}
public static void downAdjust(int[] array, int parentIndex, int length) {
// 先拿出父節(jié)點(diǎn)的值
int parentData = array[parentIndex];
// 得到左子節(jié)點(diǎn)的位置
int childIndex = 2 * parentIndex + 1;
// 當(dāng)子節(jié)點(diǎn)的下標(biāo)已經(jīng)超出數(shù)組下標(biāo)，跳出循環(huán)
while (childIndex < length) {
// 定位左子節(jié)點(diǎn)和右子節(jié)點(diǎn)的大小
if (childIndex + 1 < array.length && array[childIndex + 1] < array[childIndex]) {
childIndex++;
}
// 如果父節(jié)點(diǎn)小于任何一個(gè)子節(jié)點(diǎn)則跳出
if (parentData < array[childIndex]) {
return;
}
// 將子節(jié)點(diǎn)上浮文捶，然后下標(biāo)進(jìn)行下浮
array[parentIndex] = array[childIndex];
parentIndex = childIndex;
childIndex = 2 * parentIndex + 1;
}
// 最后跳出循環(huán)的點(diǎn)吱瘩，是父節(jié)點(diǎn)已經(jīng)不存在子節(jié)點(diǎn)了道伟，已經(jīng)遍歷到根節(jié)點(diǎn)，進(jìn)行賦值
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) {
// 構(gòu)造二叉堆
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();
}
// 放到最后一個(gè)位置
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("隊(duì)列為空");
}
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("出隊(duì)元素" + priorityQueue.deQueue());
System.out.println("出隊(duì)元素" + priorityQueue.deQueue());
System.out.println("出隊(duì)元素" + priorityQueue.deQueue());
System.out.println("出隊(duì)元素" + priorityQueue.deQueue());
System.out.println("出隊(duì)元素" + priorityQueue.deQueue());
System.out.println("出隊(duì)元素" + priorityQueue.deQueue());
System.out.println("出隊(duì)元素" + priorityQueue.deQueue());
System.out.println("出隊(duì)元素" + priorityQueue.deQueue());
System.out.println("出隊(duì)元素" + priorityQueue.deQueue());
}
}
