一、定义
堆是一种基于树的数据结构，通常用完全二叉树实现。
- 完全二叉树：除了最后一层外，其他层的节点都达到最大，并且最后一层的节点从左到右排列。
- 满二叉树：每一层的节点都被完全填满的二叉树，并且每个非叶子节点都有两个子节点
完全二叉树
1
/ \
2 3
/ \ /
4 5 6
满二叉树
1
/ \
2 3
/ \ / \
4 5 6 7
满二叉树也是完全二叉树
1.堆的特性
大顶堆（Max Heap）和小顶堆（Min Heap）是完全二叉树的一种特殊形式
- 最顶层的节点（没有父亲）称之为 root 根节点
- 在大顶堆中，任意节点 C 与它的父节点 P 符合 P.value ≥ C.value
- 小顶堆中，任意节点 C 与它的父节点 P 符合 P.value ≤ C.value
大顶堆：
10
/ \
5 3
/ \
2 4
小顶堆：
2
/ \
3 4
/ \
5 6
2.堆的存储
完全二叉树这种非线性的结构可以使用数组这种线性的结构来表示：
image.png
节点在数组中索引的计算：
从索引 0 开始存储节点数据
- 节点
的父节点索引为
，(
)
- 节点
，右孩子节点索引为
，计算的结果需要小于size
从索引 1 开始存储节点数据
- 节点
，(
)
- 节点
，右孩子节点索引为
二、实现优先级队列
1.无序数组实现
package com.hcx.algorithm.queue;
/**
* @Title: PriorityQueue1.java
* @Package com.hcx.algorithm.queue
* @Description: 优先级队列：无序数组实现
* 入队：跟普通队列一样
* 出队：优先级最高的出队
* @Author: hongcaixia
* @Date: 2025/1/12 17:33
* @Version V1.0
*/
public class PriorityQueue1<E extends Priority> implements Queue<E> {
Priority[] array;
// 数组当前大小
int size;
public PriorityQueue1(int capacity) {
array = new Priority[capacity];
}
@Override
public boolean offer(E e) {
if(isFull()){
return false;
}
array[size++] = e;
return true;
}
@Override
public E poll() {
if (isEmpty()) {
return null;
}
// 找到优先级最高的元素出队
int maxIndex = 0;
for (int i = 0; i < size; i++) {
if (array[i].getPriority() > array[maxIndex].getPriority()) {
maxIndex = i;
}
}
E e = (E) array[maxIndex];
// 出队后，该位置后的元素往前移动
if (maxIndex < size - 1) {
System.arraycopy(array, maxIndex + 1, array, maxIndex, size - maxIndex - 1);
}
// help gc
array[--size] = null;
return e;
}
@Override
public E peek() {
if (isEmpty()) {
return null;
}
// 找到优先级最高的元素
int maxIndex = 0;
for (int i = 0; i < size; i++) {
if (array[i].getPriority() > array[maxIndex].getPriority()) {
maxIndex = i;
}
}
E e = (E) array[maxIndex];
return e;
}
@Override
public boolean isEmpty() {
return size == 0;
}
@Override
public boolean isFull() {
return size == array.length;
}
}
优先级接口:
public interface Priority {
/**
* 返回对象的优先级（数字越大，优先级越高）
* @return
*/
int getPriority();
}
2.有序数组实现
package com.hcx.algorithm.queue;
/**
* @Title: PriorityQueue1.java
* @Package com.hcx.algorithm.queue
* @Description: 优先级队列：有序数组实现
* 入队：跟普通队列一样
* 出队：优先级最高的出队
* @Author: hongcaixia
* @Date: 2025/1/12 17:33
* @Version V1.0
*/
public class PriorityQueue2<E extends Priority> implements Queue<E> {
Priority[] array;
// 数组当前大小
int size;
public PriorityQueue2(int capacity) {
array = new Priority[capacity];
}
@Override
public boolean offer(E e) {
if (isFull()) {
return false;
}
// 按照优先级，插入到正确的位置
int index = size - 1;
// 从数组末尾开始往前找，如果数组中元素的优先级比当前的高，就继续往前，同时把数组的元素往后移（空出位置给当前元素）
while (index >= 0 && array[index].getPriority() > e.getPriority()) {
array[index + 1] = array[index];
index--;
}
// 找到了比当前优先级小的则退出了循环，那么index所指向的上一个就是要插入的位置
array[index + 1] = e;
size++;
return true;
}
@Override
public E poll() {
if (isEmpty()) {
return null;
}
E e = (E) array[size - 1];
// help gc
array[--size] = null;
return e;
}
@Override
public E peek() {
if (isEmpty()) {
return null;
}
return (E) array[size - 1];
}
@Override
public boolean isEmpty() {
return size == 0;
}
@Override
public boolean isFull() {
return size == array.length;
}
}
3.大顶堆实现
package com.hcx.algorithm.queue;
/**
* @Title: PriorityQueue1.java
* @Package com.hcx.algorithm.queue
* @Description: 优先级队列：使用大顶堆实现
* @Author: hongcaixia
* @Date: 2025/1/12 17:33
* @Version V1.0
*/
public class PriorityQueue3<E extends Priority> implements Queue<E> {
Priority[] array;
// 数组当前大小
int size;
public PriorityQueue3(int capacity) {
array = new Priority[capacity];
}
/**
* 1.新元素添加到数组的尾部
* 2.要符合大顶堆的特性，还需要对堆进行调整：
* 循环比较新元素与父节点的优先级，如果父节点的优先级低，则往下移动到子节点的位置，直到父节点的优先级更高或者childIndex==0
* @param e
* @return
*/
@Override
public boolean offer(E e) {
if (isFull()) {
return false;
}
int childIndex = size;
int parentIndex = (childIndex - 1) / 2;
// array[childIndex] = e;
while (childIndex > 0 && e.getPriority() > array[parentIndex].getPriority()) {
// 把父节点放到子节点上 上层的元素依次往下一层放
array[childIndex] = array[parentIndex];
// 两个指针继续往上找，直到不符合条件为止
childIndex = parentIndex;
parentIndex = (childIndex - 1) / 2;
}
array[childIndex] = e;
size++;
return true;
}
/**
* 1.移除并返回优先级最高的元素，即根元素
* 2.要符合堆的特性，还需要对堆进行调整
* - 把堆顶元素与最末尾元素进行交换，移除并返回最末尾的元素，大小减1
* - 调整堆：对堆顶的根元素依次与孩子节点作比较，如果优先级比孩子节点小，往下移动，直到父节点优先级大于孩子节点优先级或者没有孩子节点为止。
* @return
*/
@Override
public E poll() {
if (isEmpty()) {
return null;
}
// 1.堆顶元素和最末尾元素交换
Priority top = array[0];
array[0] = array[size - 1];
array[size - 1] = top;
// 2.数组大小-1
size--;
// 要返回的元素
Priority e = array[size];
// help gc
array[size] = null;
// 3.调整堆顶元素位置，依次往下找到正确的位置
downToProper(0);
return (E) e;
}
/**
* 将父节点元素下沉到正确的位置
* 从堆顶开始，依次将父元素与孩子节点中较大的进行交换，直到父元素大于两个孩子，或者没有孩子为止。
* @param parentIndex 父节点索引
*/
public void downToProper(int parentIndex) {
// 该节点的左孩子
int leftChildIndex = parentIndex * 2 + 1;
// 右孩子
int rightChildIndex = leftChildIndex + 1;
// 父节点索引 先假设本身的优先级最高，如果有比他高的 就替换掉他
int maxIndex = parentIndex;
if (leftChildIndex < size && array[leftChildIndex].getPriority() > array[parentIndex].getPriority()) {
// 左孩子节点的优先级比父节点大，将maxIndex 设置为左孩子索引
maxIndex = leftChildIndex;
}
if (rightChildIndex < size && array[rightChildIndex].getPriority() > array[parentIndex].getPriority()) {
// 右孩子节点的优先级比父节点大，将maxIndex设置为右孩子索引
maxIndex = rightChildIndex;
}
// 说明有更大的孩子节点
if (maxIndex != parentIndex) {
// 把父节点和该节点交换
Priority temp = array[maxIndex];
array[maxIndex] = array[parentIndex];
array[parentIndex] = temp;
// 继续往下找
downToProper(maxIndex);
}
}
@Override
public E peek() {
if (isEmpty()) {
return null;
}
return (E) array[0];
}
@Override
public boolean isEmpty() {
return size == 0;
}
@Override
public boolean isFull() {
return size == array.length;
}
}
总结：
- 无序数组实现优先级队列：出队效率较低：O(n)
- 有序数组实现优先级队列：入队效率较低：O(n)
- 大顶堆实现优先级队列：出队和入队：log(n)
三、Floyd建堆算法
- 找到最后一个非叶子节点
- 从最后一个非叶子节点从后向前，对每一个节点执行下沉操作（就是所有有孩子的父节点，都下沉到正确的位置（大顶堆：保证父节点是最大的，如果本身就是大的比较之后不需要下沉））
/**
* 建堆
* 1.找到最后一个非叶子节点
* 2.从最后一个非叶子节点从后向前，对每一个节点执行下沉操作（就是所有有孩子的父节点，都下沉到正确的位置（大顶堆：保证父节点是最大的，如果本身就是大的比较之后不需要下沉））
*/
private void heapify() {
// 最后一个非叶子节点索引 最后一个元素的父元素 (size-2)/2;
int index = size / 2 - 1;
for (int i = index; i >= 0; i--) {
downToProper(i);
}
}
四、堆排序
- 1.建立大顶堆
- 2.让堆顶的元素与堆底的元素交换，缩小堆的大小，调整堆
- 3.重复步骤二直到堆中仅剩一个元素
package com.hcx.algorithm.heap;
/**
* @Title: HeapSort.java
* @Package com.hcx.algorithm.heap
* @Description: 堆排序
* 1.建立大顶堆
* 2.让堆顶的元素与堆底的元素交换，缩小堆的大小，调整堆
* 3.重复步骤二直到堆中仅剩一个元素
* @Author: hongcaixia
* @Date: 2025/1/14 11:52
* @Version V1.0
*/
public class HeapSort {
static int[] arr;
int size;
public HeapSort(int[] array) {
this.arr = array;
this.size = array.length;
heapify();
}
private void heapSort() {
// 1.建堆
heapify();
while (size > 1) {
// 2.堆顶元素与堆底交换
swap(0, size - 1);
// 缩小堆
size--;
// 重建堆
downToProper(0);
}
}
public static void main(String[] args) {
int[] array = {1, 9, 3, 2, 6, 8, 7, 5};
HeapSort heapSort = new HeapSort(array);
heapSort.heapSort();
for (int i = 0;i<arr.length;i++){
System.out.println(arr[i]);
}
}
public void heapify() {
int index = (arr.length - 1) / 2 - 1;
for (int i = index; i >= 0; i--) {
downToProper(i);
}
}
/**
* 交换两个元素
* @param i
* @param j
*/
private void swap(int i,int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
/**
* 将元素下沉到正确的位置
* @param index 元素当前下标
*/
private void downToProper(int index) {
int maxIndex = index;
// 计算左右孩子节点
int leftChildIndex = 2 * index + 1;
if (leftChildIndex < size && arr[leftChildIndex] > arr[maxIndex]) {
maxIndex = leftChildIndex;
}
int rightChildIndex = leftChildIndex + 1;
if (rightChildIndex < size && arr[rightChildIndex] > arr[maxIndex]) {
maxIndex = rightChildIndex;
}
// 找到了更大的孩子 交换元素
if (maxIndex != index) {
swap(index, maxIndex);
downToProper(maxIndex);
}
}
}
五、实现堆
package com.hcx.algorithm.heap;
/**
* @Title: Heap.java
* @Package com.hcx.algorithm.heap
* @Description: 堆
* @Author: hongcaixia
* @Date: 2025/1/14 18:14
* @Version V1.0
*/
public class Heap {
int[] arr;
int size;
// 是否是大顶堆
boolean maxHeapFlag;
public int size() {
return size;
}
public Heap(int capacity, boolean maxHeapFlag) {
this.arr = new int[capacity];
this.maxHeapFlag = maxHeapFlag;
}
public Heap(int[] arr, boolean maxHeapFlag) {
this.arr = arr;
this.size = arr.length;
this.maxHeapFlag = maxHeapFlag;
heapify();
}
/**
* 获取堆顶元素
*
* @return
*/
public int peek() {
return arr[0];
}
/**
* 移除堆顶元素并返回
* 1.堆顶元素和末尾元素交换
* 2.size--
* 3.堆顶的元素依次下沉到正确的位置
*
* @return
*/
public int poll() {
int top = arr[0];
swap(0, size - 1);
size--;
// 对堆顶元素依次执行下沉操作到正确位置
downToProper(0);
return top;
}
/**
* 移除指定索引的元素并返回
*
* @param index
* @return
*/
public int poll(int index) {
int ele = arr[index];
swap(index, size - 1);
size--;
downToProper(index);
return ele;
}
/**
* 替换堆顶元素
*
* @param replaced
*/
public void replaceTop(int replaced) {
arr[0] = replaced;
downToProper(0);
}
/**
* 在堆的尾部添加元素
*
* @param offered
* @return
*/
public void offer(int offered) {
if (size == arr.length) {
arrGrow();
}
upToProper(offered, size);
size++;
}
/**
* 将元素上浮到正确位置
*
* @param offered 元素
* @param index 元素当前下标
*/
private void upToProper(int offered, int index) {
int childIndex = index;
while (childIndex > 0) {
// 计算他的父节点下标
int parentIndex = (childIndex - 1) >> 1;
boolean compare = maxHeapFlag ? offered > arr[parentIndex] : offered < arr[parentIndex];
if (compare) {
// 父节点往下移动
arr[childIndex] = arr[parentIndex];
} else {
break;
}
// 改变孩子节点为当前的父节点
childIndex = parentIndex;
}
arr[childIndex] = offered;
}
/**
* 将元素下沉到正确的位置
*
* @param index 元素当前下标
*/
private void downToProper(int index) {
int minIndex = index;
// 计算左右孩子节点
int leftChildIndex = 2 * index + 1;
if ((leftChildIndex < size) && (maxHeapFlag ? arr[leftChildIndex] > arr[minIndex] : arr[leftChildIndex] < arr[minIndex])) {
minIndex = leftChildIndex;
}
int rightChildIndex = leftChildIndex + 1;
if ((rightChildIndex < size) && (maxHeapFlag ? arr[rightChildIndex] > arr[minIndex] : arr[rightChildIndex] < arr[minIndex])) {
minIndex = rightChildIndex;
}
// 找到了更大的孩子 交换元素
if (minIndex != index) {
swap(index, minIndex);
downToProper(minIndex);
}
}
/**
* 交换两个元素
*
* @param i
* @param j
*/
private void swap(int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
/**
* 建堆
* 1.找到最后一个非叶子节点
* 2.从最后一个非叶子节点从后向前，对每一个节点执行下沉操作（就是所有有孩子的父节点，都下沉到正确的位置（大顶堆：保证父节点是最大的，如果本身就是大的比较之后不需要下沉））
*/
private void heapify() {
// 最后一个非叶子节点索引 最后一个元素的父元素 (size-2)/2;
int index = size / 2 - 1;
for (int i = index; i >= 0; i--) {
downToProper(i);
}
}
public boolean isFull() {
return size == arr.length;
}
/**
* 数组扩容：每次扩为原来的1.5倍
*/
private void arrGrow() {
int capacity = size + (size >> 1);
int[] newArr = new int[capacity];
System.arraycopy(arr, 0, newArr, 0, size);
arr = newArr;
}
}
六、Leetcode703.数据流中的第K大元素
package com.hcx.algorithm.heap;
/**
* @Title: KthLargest.java
* @Package com.hcx.algorithm.heap
* @Description: Leetcode703.数据流中的第K大元素
* @Author: hongcaixia
* @Date: 2025/1/14 16:42
* @Version V1.0
*/
public class KthLargest {
MinHeap minHeap;
public KthLargest(int k, int[] nums) {
minHeap = new MinHeap(k);
for (int num : nums) {
add(num);
}
}
/**
* 插入数据流后，返回当前第k大元素
* @param val
* @return
*/
public int add(int val) {
// 堆没满
if(!minHeap.isFull()){
minHeap.offer(val);
}else if (val > minHeap.peek()) {
minHeap.replaceTop(val);
}
return minHeap.peek();
}
}
七、Leetcode295.数据流的中位数
分成两部分：一部分是较小的，一部分是较大的
- 较小数据中让最大的在堆顶，较大的数据中让最小的在堆顶
- 堆顶的两个元素就是中间的两个
- 左边是大顶堆 右边是小顶堆
public class MedianFinder {
// 大顶堆，存储前半部分元素；
static Heap maxHeap = new Heap(10, true);
// 小顶堆，存储后半部分元素
static Heap minHeap = new Heap(10, false);
public static void addNum(int num) {
if (maxHeap.size == minHeap.size) {
//元素加入左边 加入左边之前 要保证元素是最小的 先加入右边，再从右边的堆顶取出最小的加入左边
minHeap.offer(num);
maxHeap.offer(minHeap.poll());
} else {
// 元素加入右边，加入右边之前，要保证元素是大的，先加入左边，再从左边的堆顶取出最大的加入右边
maxHeap.offer(num);
minHeap.offer(maxHeap.poll());
}
}
public static double findMedian() {
if (maxHeap.size == minHeap.size) {
return (maxHeap.peek() + minHeap.peek()) / 2.0;
} else {
return maxHeap.peek();
}
}
}
使用jdk的堆实现：
class MedianFinder {
// 使用优先级队列 默认是小顶堆
// 存储前半部分元素
static PriorityQueue<Integer> maxQueue = new PriorityQueue<>((o1, o2) -> Integer.compare(o2, o1));
// 存储后半部分元素
static PriorityQueue<Integer> minQueue = new PriorityQueue<>((o1, o2) -> Integer.compare(o1, o2));
public void addNum(int num) {
// 往前半部分加
if (minQueue.size() == maxQueue.size()) {
minQueue.offer(num);
maxQueue.offer(minQueue.poll());
} else {
// 往右边加 加在右边的要保证是大的
maxQueue.offer(num);
minQueue.offer(maxQueue.poll());
}
}
public double findMedian() {
if(maxQueue.size() == minQueue.size()){
return (maxQueue.peek() + minQueue.peek()) / 2.0;
}else{
return maxQueue.peek();
}
}
}
救命，这个实现方法在力扣上一直不对，评论区的大神救救孩子，本地是好的，找不出来哪里的问题。
