当前位置：首页 > news >正文

数据结构与算法 - 堆

news 来源：原创 2024/9/20 10:53:07

1. 建堆

Floyd建堆算法作者（也是之前龟兔赛跑判环作者）：

①找到最后一个非叶子节点
②从后往前，对每个节点执行下潜

一些规律

一棵满二叉树节点个数为2^h - 1，如下例中高度h = 3节点数是2 ^ 3 - 1 = 7
非叶子节点范围为[0, size/2 - 1]

算法时间复杂度分析

下面看交换次数的推导：设节点高度为3

	本层节点数	高度	下潜最多交换次数（高度-1）
4567 这层	4	1	0
23这层	2	2	1
1这层	1	3	2

每一层的交换次数为：节点个数 * 此节点交换次数，总的交换次数为

即

推导出 2^h - h - 1，其中2^h ≈ n，h ≈ log_2(n)，因此时间复杂度为O(n)

算法描述：

heapify建立大根堆
将堆顶与堆底交换（最大元素被交换到堆底），缩小并下潜调整堆
重复第二步直至堆里剩一个元素

大根堆：

package com.itheima.datastructure.Heap;import java.util.Arrays;/*** 大顶堆*/
public class MaxHeap {int[] array;int size;public MaxHeap(int capacity) {this.array = new int[capacity];}public boolean isEmpty() {return size == 0;}public boolean isFull() {return size == array.length;}/*** 获取堆顶元素** @return 堆顶元素*/public int peek() {if(isEmpty()) {return -1;}return array[0];}/*** 删除堆顶元素** @return 堆顶元素*/public int poll() {if(isEmpty()) {return -1;}int top = array[0];swap(0, size - 1);size--;down(0);return top;}/*** 删除指定索引处元素** @param index 索引* @return 被删除元素*/public int poll(int index) {if(isEmpty()) {return -1;}int deleted = array[index];up(Integer.MAX_VALUE, index);poll();return deleted;}/*** 替换堆顶元素** @param replaced 新元素*/public void replace(int replaced) {array[0] = replaced;down(0);}/*** 堆的尾部添加元素** @param offered 新元素* @return 是否添加成功*/public boolean offer(int offered) {if(isFull()) {return false;}up(offered, size);size++;return true;}// 将 offered 元素上浮: 直至 offered 小于父元素或到堆顶private void up(int offered, int index) {int child = index;while (child > 0) {int parent = (child - 1) / 2;if (offered > array[parent]) {array[child] = array[parent];} else {break;}child = parent;}array[child] = offered;}public MaxHeap(int[] array) {this.array = array;this.size = array.length;heapify();}// 建堆private void heapify() {// 如何找到最后这个非叶子节点  size / 2 - 1for (int i = size / 2 - 1; i >= 0; i--) {down(i);}}// 将 parent 索引处的元素下潜: 与两个孩子较大者交换, 直至没孩子或孩子没它大private void down(int parent) {int left = parent * 2 + 1;int right = left + 1;int max = parent;if (left < size && array[left] > array[max]) {max = left;}if (right < size && array[right] > array[max]) {max = right;}if (max != parent) { // 找到了更大的孩子swap(max, parent);down(max);}}// 交换两个索引处的元素private void swap(int i, int j) {int t = array[i];array[i] = array[j];array[j] = t;}public static void main(String[] args) {int[] array = {2, 3, 1, 7, 6, 4, 5};MaxHeap heap = new MaxHeap(array);System.out.println(Arrays.toString(heap.array));while (heap.size > 1) {heap.swap(0, heap.size - 1);heap.size--;heap.down(0);}System.out.println(Arrays.toString(heap.array));}
}

小根堆：

package com.itheima.datastructure.heap;public class MinHeap {int[] array;int size;public MinHeap(int capacity) {this.array = new int[capacity];}public boolean isFull() {return size == array.length;}/*** 获取堆顶元素** @return 堆顶元素*/public int peek() {return array[0];}/*** 删除堆顶元素** @return 堆顶元素*/public int poll() {int top = array[0];swap(0, size - 1);size--;down(0);return top;}/*** 删除指定索引处元素** @param index 索引* @return 被删除元素*/public int poll(int index) {int deleted = array[index];up(Integer.MIN_VALUE, index);poll();return deleted;}/*** 替换堆顶元素** @param replaced 新元素*/public void replace(int replaced) {array[0] = replaced;down(0);}/*** 堆的尾部添加元素** @param offered 新元素* @return 是否添加成功*/public boolean offer(int offered) {if (size == array.length) {return false;}up(offered, size);size++;return true;}// 将 offered 元素上浮: 直至 offered 小于父元素或到堆顶private void up(int offered, int index) {int child = index;while (child > 0) {int parent = (child - 1) / 2;if (offered < array[parent]) {array[child] = array[parent];} else {break;}child = parent;}array[child] = offered;}public MinHeap(int[] array) {this.array = array;this.size = array.length;heapify();}// 建堆private void heapify() {// 如何找到最后这个非叶子节点  size / 2 - 1for (int i = size / 2 - 1; i >= 0; i--) {down(i);}}// 将 parent 索引处的元素下潜: 与两个孩子较大者交换, 直至没孩子或孩子没它大private void down(int parent) {int left = parent * 2 + 1;int right = left + 1;int min = parent;if (left < size && array[left] < array[min]) {min = left;}if (right < size && array[right] < array[min]) {min = right;}if (min != parent) { // 找到了更大的孩子swap(min, parent);down(min);}}// 交换两个索引处的元素private void swap(int i, int j) {int t = array[i];array[i] = array[j];array[j] = t;}
}

2. 习题

2.1 堆排序

package com.itheima.datastructure.heap;import java.util.Arrays;public class E01HeapSort {public static void sort(int[] array) {// 1. 建堆int size = array.length;heapify(array, size);while (size > 1) {// 2. 将堆顶元素交换至堆底swap(array, 0, size - 1);// 堆大小减一size--;// 重新调整堆down(array, 0, size);}}// 建堆private static void heapify(int[] array, int size) {for (int i = size / 2 - 1; i >= 0; i--) {down(array, i, size);}}// 下潜private static void down(int[] array, int parent, int size) {int left = parent * 2 + 1;int right = left + 1;int max = parent;if (left < size && array[left] > array[max]) {max = left;}if (right < size && array[right] > array[max]) {max = right;}if (max != parent) { // 找到了更大的孩子swap(array, max, parent);down(array, max, size);}}// 交换private static void swap(int[] array, int i, int j) {int t = array[i];array[i] = array[j];array[j] = t;}public static void main(String[] args) {int[] array = {2, 3, 1, 7, 6, 4, 5};sort(array);System.out.println(Arrays.toString(array));}
}

2.2 数组中第K大元素

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例 1:

输入: [3,2,1,5,6,4], k = 2
输出: 5

示例 2:

输入: [3,2,3,1,2,4,5,5,6], k = 4
输出: 4

提示：

1 <= k <= nums.length <= 10^5
-10^4 <= nums[i] <= 10^4

解法一：小根堆

class Solution {static class MinHeap {int[] array;int size;public MinHeap(int capacity) {array = new int[capacity];}public int peek() {return array[0];}public boolean offer(int offered) {if (size == array.length) {return false;}up(offered);size++;return true;}public void replace(int replaced) {array[0] = replaced;down(0);}private void up(int offered) {int child = size;while (child > 0) {int parent = (child - 1) >> 1;if (offered < array[parent]) {array[child] = array[parent];} else {break;}child = parent;}array[child] = offered;}private void down(int parent) {int left = (parent << 1) + 1;int right = left + 1;int min = parent;if (left < size && array[left] < array[min]) {min = left;}if (right < size && array[right] < array[min]) {min = right;}if (min != parent) {swap(min, parent);down(min);}}// 交换两个索引处的元素private void swap(int i, int j) {int t = array[i];array[i] = array[j];array[j] = t;}}public int findKthLargest(int[] nums, int k) {MinHeap heap = new MinHeap(k);// 先将k个元素入堆for (int i = 0; i < k; i++) {heap.offer(nums[i]);}// 将剩余的元素与堆顶元素比较，如果比堆顶元素大则替换。比较完成后，堆顶元素即为第k大的元素（小根堆）for (int i = k; i < nums.length; i++) {if (nums[i] > heap.peek()) {heap.replace(nums[i]);}}return heap.peek();}
}

解法二：优先级队列

class Solution {public int findKthLargest(int[] nums, int k) {PriorityQueue<Integer> minHeap = new PriorityQueue<>();  // 默认底层实现是小根堆for (int num : nums) {minHeap.offer(num);if(minHeap.size() > k) {minHeap.poll();}}return minHeap.peek();}
}

2.3 数据流的中的第K大元素

设计一个找到数据流中第 k 大元素的类（class）。注意是排序后的第 k 大元素，不是第 k 个不同的元素。

请实现 KthLargest 类：

KthLargest(int k, int[] nums) 使用整数 k 和整数流 nums 初始化对象。
int add(int val) 将 val 插入数据流 nums 后，返回当前数据流中第 k 大的元素。

示例：

输入：
["KthLargest", "add", "add", "add", "add", "add"]
[[3, [4, 5, 8, 2]], [3], [5], [10], [9], [4]]
输出：
[null, 4, 5, 5, 8, 8]解释：
KthLargest kthLargest = new KthLargest(3, [4, 5, 8, 2]);
kthLargest.add(3);   // return 4
kthLargest.add(5);   // return 5
kthLargest.add(10);  // return 5
kthLargest.add(9);   // return 8
kthLargest.add(4);   // return 8

提示：

1 <= k <= 10^4
0 <= nums.length <= 10^4
-10^4 <= nums[i] <= 10^4
-10^4 <= val <= 10^4
最多调用 add 方法 10^4 次
题目数据保证，在查找第 k 大元素时，数组中至少有 k 个元素

解法一：小根堆

class KthLargest {static class MinHeap {int[] array;int size;public MinHeap(int capacity) {array = new int[capacity];}public boolean isFull() {return size == array.length;}public int peek() {return array[0];}public boolean offer(int offered) {if (size == array.length) {return false;}up(offered);size++;return true;}public void replace(int replaced) {array[0] = replaced;down(0);}private void up(int offered) {int child = size;while (child > 0) {int parent = (child - 1) >> 1;if (offered < array[parent]) {array[child] = array[parent];} else {break;}child = parent;}array[child] = offered;}private void down(int parent) {int left = (parent << 1) + 1;int right = left + 1;int min = parent;if (left < size && array[left] < array[min]) {min = left;}if (right < size && array[right] < array[min]) {min = right;}if (min != parent) {swap(min, parent);down(min);}}// 交换两个索引处的元素private void swap(int i, int j) {int t = array[i];array[i] = array[j];array[j] = t;}}private MinHeap heap;public KthLargest(int k, int[] nums) {heap = new MinHeap(k);for(int i = 0; i < nums.length; i++) {add(nums[i]);}}public int add(int val) {if(!heap.isFull()) {heap.offer(val);} else if(val > heap.peek()) {heap.replace(val);}return heap.peek();}
}/*** Your KthLargest object will be instantiated and called as such:* KthLargest obj = new KthLargest(k, nums);* int param_1 = obj.add(val);*/

2.4 数据流的中位数

中位数是有序整数列表中的中间值。如果列表的大小是偶数，则没有中间值，中位数是两个中间值的平均值。

例如 arr = [2,3,4] 的中位数是 3 。
例如 arr = [2,3] 的中位数是 (2 + 3) / 2 = 2.5 。

实现 MedianFinder 类:

MedianFinder() 初始化 MedianFinder 对象。
void addNum(int num) 将数据流中的整数 num 添加到数据结构中。
double findMedian() 返回到目前为止所有元素的中位数。与实际答案相差 10-5 以内的答案将被接受。

示例 1：

输入
["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"]
[[], [1], [2], [], [3], []]
输出
[null, null, null, 1.5, null, 2.0]解释
MedianFinder medianFinder = new MedianFinder();
medianFinder.addNum(1);    // arr = [1]
medianFinder.addNum(2);    // arr = [1, 2]
medianFinder.findMedian(); // 返回 1.5 ((1 + 2) / 2)
medianFinder.addNum(3);    // arr[1, 2, 3]
medianFinder.findMedian(); // return 2.0

提示:

-10^5 <= num <= 10^5
在调用 findMedian 之前，数据结构中至少有一个元素
最多 5 * 10^4 次调用 addNum 和 findMedian

解法一：大根堆 + 小根堆

解题思路：为了保持两边数据量的平衡：

两边个数一样时，左边个数加一；两边个数不一样时，右边个数加一；
左边个数加一时，应该先将新增元素加入右边，再挑右边最小元素加入左边；
右边个数加一时，应该先将新增元素加入左边，再挑左边最大元素加入右边；

class MedianFinder {public static class Heap {int[] array;int size;boolean max;public int size() {return size;}public Heap(int capacity, boolean max) {this.array = new int[capacity];this.max = max;}/*** 获取堆顶元素** @return 堆顶元素*/public int peek() {return array[0];}/*** 删除堆顶元素** @return 堆顶元素*/public int poll() {int top = array[0];swap(0, size - 1);size--;down(0);return top;}/*** 删除指定索引处元素** @param index 索引* @return 被删除元素*/public int poll(int index) {int deleted = array[index];swap(index, size - 1);size--;down(index);return deleted;}/*** 替换堆顶元素** @param replaced 新元素*/public void replace(int replaced) {array[0] = replaced;down(0);}/*** 堆的尾部添加元素** @param offered 新元素*/public void offer(int offered) {if (size == array.length) {grow();}up(offered);size++;}/*** 扩容*/private void grow() {int capacity = size + (size >> 1);int[] newArray = new int[capacity];System.arraycopy(array, 0, newArray, 0, size);array = newArray;}// 将 offered 元素上浮: 直至 offered 小于父元素或到堆顶private void up(int offered) {int child = size;while (child > 0) {int parent = (child - 1) / 2;boolean cmp = max ? offered > array[parent] : offered < array[parent];if (cmp) {array[child] = array[parent];} else {break;}child = parent;}array[child] = offered;}public Heap(int[] array, boolean max) {this.array = array;this.size = array.length;this.max = max;heapify();}// 建堆private void heapify() {// 如何找到最后这个非叶子节点 size / 2 - 1for (int i = size / 2 - 1; i >= 0; i--) {down(i);}}// 将 parent 索引处的元素下潜: 与两个孩子较大者交换, 直至没孩子或孩子没它大private void down(int parent) {int left = parent * 2 + 1;int right = left + 1;int min = parent;if (left < size && (max ? array[left] > array[min] : array[left] < array[min])) {min = left;}if (right < size && (max ? array[right] > array[min] : array[right] < array[min])) {min = right;}if (min != parent) { // 找到了更大的孩子swap(min, parent);down(min);}}// 交换两个索引处的元素private void swap(int i, int j) {int t = array[i];array[i] = array[j];array[j] = t;}}private Heap left = new Heap(10, false);  // 大根堆private Heap right = new Heap(10, true);  // 小根堆public MedianFinder() {}public void addNum(int num) {// 两边个数一样时，左边个数加一。 左边个数加一时，应该先将新增元素加入右边，再挑 右边最小元素 加入左边if(left.size() == right.size()) {  right.offer(num);left.offer(right.poll());} else {  // 两边个数不一样时，右边个数加一。 右边个数加一时，应该先将新增元素加入左边，再挑 左边最大元素 加入右边left.offer(num);right.offer(left.poll());}}public double findMedian() {if(left.size() == right.size()) {return (left.peek() + right.peek()) / 2.0;} else {  // 不等的情况下，是左边多一个元素return left.peek();}}
}/*** Your MedianFinder object will be instantiated and called as such:* MedianFinder obj = new MedianFinder();* obj.addNum(num);* double param_2 = obj.findMedian();*/

解法二：优先队列

package com.itheima.datastructure.Heap;import java.util.PriorityQueue;public class MedianFinder {PriorityQueue<Integer> left = new PriorityQueue<>((a, b) -> b - a);PriorityQueue<Integer> right = new PriorityQueue<>();public MedianFinder() {}public void addNum(int num) {// 两边个数一样时，左边个数加一。 左边个数加一时，应该先将新增元素加入右边，再挑 右边最小元素 加入左边if(left.size() == right.size()) {right.offer(num);left.offer(right.poll());} else {// 两边个数不一样时，右边个数加一。 右边个数加一时，应该先将新增元素加入左边，再挑 左边最大元素 加入右边left.offer(num);right.offer(left.poll());}}public double findMedian() {if(left.size() == right.size()) {return (left.peek() + right.peek()) / 2.0;} else {return left.peek();}}
}