本篇是上篇 数据结构与算法(三):树 和 二叉树 的延续。
二叉堆 是一种特殊的堆,本质上是一种完全二叉树。二叉堆有两个类型:最大堆 和 最小堆。
优先队列中,元素被赋予优先级。当访问元素时,具有最高优先级的元素最先删除。优先队列具有最高级先出 (first in, largest out)的行为特征。通常采用堆数据结构来实现。
二叉堆
最大堆
最大堆:任何一个父节点的值,都 大于 或 等于 它左、右子节点的值,堆顶 是整个堆中的 最大 元素。
最小堆
最小堆:任何一个父节点的值,都 小于 或 等于 它左、右孩子节点的值,堆顶 是整个堆中的 最小 元素。
二叉堆的操作
二叉堆的操作主要有 插入、删除、构建 三种操作。二
二叉堆的操作都基于堆的 自我调整 。所谓堆的自我调整,就是把一个不符合堆性质的完全二叉树,通过上浮 或 下沉 的方式调整成一个堆。
二叉堆 是实现 堆排序 及 优先队列 的基础。
插入节点
从末尾插入节点,插入的节点和需要和父节点进行比较:
删除节点
删除节点和插入节点的过程正好相反,所删除的是处于堆顶的节点。
删除堆顶节点,把堆的最后一个元素补充到堆顶的位置,然后于左、右子节点比较,根据是最大堆或最小堆来判断是否下沉。
构建二叉堆
构建二叉堆,就是把一个无序的完全二叉树调整为二叉堆,本质是让所有 非叶子节点依次 “下沉”。
非叶子节点与左、右子节点比较,根据最大堆或最小堆来决定是否下沉。
堆的插入操作是插入节点的上浮,删除操作是插入节点的下沉。
这两个操作的平均交换次数都是堆高度的一半,所以时间复杂度是 Ο(logn) ,而构建堆的时间复杂度是 Ο*(n*) 。
二叉堆代码实现
二叉堆虽然是一个完全二叉树,但存储方式是顺序存储,而不是链式存储。在存储的物理结构上是采用数组存储。
一个数组中,在没有左、右指针的情况下,首先将数组最后一个元素(right = array.length - 1) 作为最后的叶子节点,再确定一个父节点的下标(parent = (right - 1) / 2),那它的左节点就是 left = parent * 2 + 1,右子节点就是 right = parent * 2 + 2 。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60
| package com.datastructure.alg.binaryheap;
import java.util.Arrays;
public class BinaryHeap {
public static void downAdjust(int[] array, int parentIndex, int length) { int temp = array[parentIndex]; int childIndex = 2 * parentIndex + 1; while (childIndex < length) { if (childIndex + 1 < length && array[childIndex + 1] < array[childIndex]) { childIndex++; }
if (temp <= array[childIndex]) { break; }
array[parentIndex] = array[childIndex]; parentIndex = childIndex; childIndex = 2 * childIndex + 1; } array[parentIndex] = temp; }
public static void buildHeap(int[] array) {
for (int i = (array.length - 2) / 2; i >= 0; i--) { downAdjust(array, i, array.length); System.out.println("遍历:" + Arrays.toString(array)); } }
public static void main(String[] args) { int[] array = new int[]{4, 2, 11, 10, 8, 3, 9, 1, 5, 6, 7}; System.out.println("原始:" + Arrays.toString(array)); buildHeap(array); System.out.println("最终:" + Arrays.toString(array)); } }
|
优先队列
普通队列是一种是先进先出(FIFO)的数据结构。入队列,新元素在队列尾追加;出队列,队头元素最先被移出。
优先队列,元素被赋予优先级。当访问元素时,具有最高优先级的元素最先删除。优先队列具有最高级先出 (first in, largest out)的行为特征。通常采用堆数据结构来实现。
特点
优先队列则不再遵循先入先出的原则,而是分为两种情况:
- 最大优先队列,无论入队顺序如何,都是当前最大的元素优先出队。
- 最小优先队列,无论入队顺序如何,都是当前最小的元素优先出队。
例如,有一个最大优先队列,可能最大元素并不是队头元素,但出队时仍然是此最大元素首先出队。
基于二叉堆的特性,即最大堆的堆顶是整个堆中的最大元素,最小堆的堆顶是整个堆中的最小元素。
因此,可以用最大堆来实现最大优先队列,每一次入队操作就是堆的插入操作,每一次出队操作就是删除堆顶节点。
入队
入队:就是插入节点的操作,在堆的末尾插入,与父节点比较,大于则上浮到合适位置。
出队
出队:就是堆顶节点的删除操作,然后把最后一个节点替换到堆顶位置,再与左、右子节点比较,如果子节点更大则上浮。
二叉堆节点 上浮 和 下沉 的时间复杂度都是 Ο(logn) ,所以优先队列入队和出队的时间复杂度也是 Ο(logn) 。
代码实现
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102
| import java.util.Arrays;
public class PriorityQueue {
private int[] array; private int size;
public PriorityQueue() { this.array = new int[32]; }
public void enQueue(int key) { if (size >= array.length) { resize(); } array[size++] = key; upAdjust(); }
public int deQueue() throws Exception { if (size <= 0) { throw new Exception("the queue is empty"); }
int head = array[0]; array[0] = array[--size]; downAdjust(); return head; }
private void upAdjust() { int childIndex = size - 1; int parentIndex = childIndex / 2; int temp = array[childIndex]; while (childIndex > 0 && temp > array[parentIndex]) { array[childIndex] = array[parentIndex]; childIndex = parentIndex; parentIndex = parentIndex / 2; } array[childIndex] = temp;
}
private void downAdjust() { int parentIndex = 0; int temp = array[parentIndex]; int childIndex = 1; 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 * childIndex + 1; } array[parentIndex] = temp; }
private void resize() { int newSize = this.size * 2; this.array = Arrays.copyOf(this.array, newSize); }
public static void main(String[] args) throws Exception { PriorityQueue priorityQueue = new PriorityQueue(); priorityQueue.enQueue(3); priorityQueue.enQueue(5); priorityQueue.enQueue(10); priorityQueue.enQueue(2); priorityQueue.enQueue(7);
System.out.println("出队元素:" + priorityQueue.deQueue()); System.out.println("出队元素:" + priorityQueue.deQueue()); } }
|
更多参考
- 二叉堆(三)之 Java的实现 。
- 数据结构与算法系列 目录 此系列博文非常不错。