数据结构与算法——Java实现 32.堆

目录

堆

大顶堆

威廉姆斯建堆算法

Floyd建堆算法

Floyd建堆算法复杂度

大顶堆代码实现

---

人的想法和感受是会随着时间的认知改变而改变，

原来你笃定不会变的事，也会在最后一刻变得释然

                                                                —— 24.10.10

堆

堆是基于二叉树实现的数据结构

大顶堆任意一个父节点的权值要大于其两个孩子的权值，同一层节点的权值大小无关

小顶堆任意一个父节点的权值要小于其两个孩子的权值，同一层节点的权值大小无关

---

大顶堆

威廉姆斯建堆算法

不断的向堆中添加节点，添加时与堆最末尾元素进行比较，如果权值大于最末尾元素，则不断上调与其（最末尾元素，不断更新）父元素比较，直到找到小于堆中某元素的值或更新到堆顶元素

时间复杂度为O(n*logn)

---

Floyd建堆算法

1.找到最后一个非叶子节点 索引【size / 2 - 1】

2.从后向前，对每个结点执行下潜（与其左右孩子节点中的较大值进行交换）

Floyd建堆算法复杂度

复杂度与堆的高度h有关，高度从下往上由1开始依次相加，交换次数为h-1，总交换次数为每个节点的总高度除以结点所在每一层的高度 *（高度-1）之和

i指的是结点的高度

h指的是堆的总高度

推导出

        O(n) = 2^h-h-1

        ∵ 2^h ≈ n，h ≈ log2n

因此Floyd建堆算法的时间复杂度为O(n)

---

大顶堆代码实现

一、建堆方法（buildHeap）

该方法通过从最后一个非叶子节点开始，逐个节点进行下潜操作，确保堆的性质。循环从size / 2 - 1开始是正确的，因为这是最后一个非叶子节点的索引。对于每个节点，调用down方法进行下潜操作，以确保节点的值不小于其子节点的值。

二、下潜方法（heapifyDown）

1. 正确地计算了当前节点的左子节点索引（left = parent * 2 + 1）和右子节点索引（right = left + 1）。
2. 找到当前节点及其两个子节点中的最大值索引（max），并与当前节点索引（parent）进行比较。如果找到了更大的子节点，则进行交换，并递归地对新的位置进行下潜操作。

三、交换方法（swap）

该方法简单地交换两个索引处的元素值

四、获取堆顶元素方法（peek）

如果堆为空（size == 0），返回 -1，否则返回堆顶元素（array[0]）

五、删除堆顶元素方法（poll）

1. 如果堆为空，返回 -1。
2. 保存堆顶元素，将堆顶元素与最后一个元素交换，然后减小堆的大小。
3. 对新的堆顶元素进行下潜操作，以维持堆的性质。

六、删除指定索引处的元素方法（poll(int index)）

1. 如果堆为空，返回 -1。
2. 保存指定索引处的元素，将其与最后一个元素交换，然后减小堆的大小。
3. 对交换后的元素从指定索引处进行下潜操作，以维持堆的性质。

七、替换堆顶元素方法（replace）

将新元素赋值给堆顶元素，然后对堆顶元素进行下潜操作，以维持堆的性质。

八、添加元素方法（offer）

1. 如果堆已满，返回 false。
2. 将新元素添加到堆的末尾，然后调用up方法对新元素进行上浮操作，以维持堆的性质。最后增加堆的大小。

九、上浮方法（heapifyUp）

从新添加元素的索引位置开始，向上比较新元素与父节点的值。如果新元素大于父节点，则交换它们，并继续向上比较，直到新元素小于父节点或者到达堆顶。

import java.util.Arrays;public class MaxHeap {int[] heapArray;int size;public MaxHeap(int capacity) {heapArray = new int[capacity];}public MaxHeap(int[] initialArray) {heapArray = new int[initialArray.length];System.arraycopy(initialArray, 0, heapArray, 0, initialArray.length);size = initialArray.length;buildHeap();}private void buildHeap() {for (int i = size / 2 - 1; i >= 0; i--) {heapifyDown(i);}}private void heapifyDown(int index) {int leftChildIndex = 2 * index + 1;int rightChildIndex = 2 * index + 2;int largestIndex = index;if (leftChildIndex < size && heapArray[leftChildIndex] > heapArray[largestIndex]) {largestIndex = leftChildIndex;}if (rightChildIndex < size && heapArray[rightChildIndex] > heapArray[largestIndex]) {largestIndex = rightChildIndex;}if (largestIndex!= index) {swap(index, largestIndex);heapifyDown(largestIndex);}}private void swap(int i, int j) {int temp = heapArray[i];heapArray[i] = heapArray[j];heapArray[j] = temp;}public int peek() {if (size == 0) {return -1;}return heapArray[0];}public int poll() {if (size == 0) {return -1;}int maxValue = heapArray[0];heapArray[0] = heapArray[size - 1];size--;heapifyDown(0);return maxValue;}public int poll(int index) {if (size == 0 || index >= size) {return -1;}int removedValue = heapArray[index];heapArray[index] = heapArray[size - 1];size--;heapifyDown(index);return removedValue;}public void replace(int newValue) {if (size == 0) {return;}heapArray[0] = newValue;heapifyDown(0);}public boolean offer(int value) {if (size == heapArray.length) {return false;}heapArray[size] = value;heapifyUp(size);size++;return true;}private void heapifyUp(int index) {int parentIndex = (index - 1) / 2;while (index > 0 && heapArray[index] > heapArray[parentIndex]) {swap(index, parentIndex);index = parentIndex;parentIndex = (index - 1) / 2;}}public static void main(String[] args) {int[] initialArray = {1, 2, 3, 4, 5, 6, 7};MaxHeap maxHeap = new MaxHeap(initialArray);System.out.println(Arrays.toString(maxHeap.heapArray));// [7, 5, 6, 4, 2, 1, 3]maxHeap.replace(5);System.out.println(Arrays.toString(maxHeap.heapArray));// [6, 5, 5, 4, 2, 1, 3]maxHeap.poll(2);System.out.println(Arrays.toString(maxHeap.heapArray));// [6, 5, 3, 4, 2, 1, 3]System.out.println(maxHeap.peek());// 6maxHeap.poll();System.out.println(Arrays.toString(maxHeap.heapArray));// [5, 4, 3, 1, 2, 1, 3]System.out.println(maxHeap.offer(5));// trueSystem.out.println(Arrays.toString(maxHeap.heapArray));// [5, 4, 5, 1, 2, 3, 3]maxHeap.poll();System.out.println(Arrays.toString(maxHeap.heapArray));// [5, 4, 3, 1, 2, 3, 3]maxHeap.offer(9);System.out.println(Arrays.toString(maxHeap.heapArray));// [9, 4, 5, 1, 2, 3, 3]}
}