目录
一.概念
堆（Heap）在计算机科学中是一种数据结构，用于存储和管理动态分配的内存。堆的主要特点是它是一个有序的完全二叉树，每个节点的值都大于或小于其子节点的值，称为最小堆或最大堆。
堆常用于实现优先队列、堆排序、图算法等。堆排序是一种基于堆数据结构的排序算法，它具有稳定性和不需要额外的内存空间的优点。优先队列是一种数据结构，支持插入和删除最大或最小元素的操作，并根据优先级对元素进行排序。堆可以用于高效地实现优先队列。
同时，堆还有其他用途，比如内存管理中的动态内存分配，垃圾回收算法中的对象分配等
二.堆中最重要三个方法
1.heapify() 调整堆
通过调整堆，可以让不符合堆特性的节点转化为符合堆特性的序列
2.up() 上浮
在offer（）向末尾添加元素时，通过上浮操作，插入到合适的位置
3.down() 下潜
在poll()方法从堆顶取出元素后，通过下潜方法，下潜到合适的位置
三.大顶堆
大顶堆（Max Heap）是一种堆的实现方式，它满足以下性质：
- 每个节点的值都大于或等于其子节点的值。
- 堆顶元素（根节点）是整个堆中最大的元素。
在大顶堆中，任意节点的值都大于或等于其子节点的值，但是它们之间的顺序并没有固定的要求，即左右子节点之间的大小关系并不要求一定是有序的。
大顶堆可以通过数组或完全二叉树来实现。在数组中，堆的根节点存储在索引为0的位置，而任意节点i的左子节点存储在索引为2i+1的位置，右子节点存储在索引为2i+2的位置。
大顶堆的常见操作包括：
- 插入元素：将元素插入堆的底部，然后通过调整堆的结构将其置于正确的位置上，以保持堆的性质。
- 删除堆顶元素：将堆顶元素与堆底元素交换，然后删除堆底元素，再通过调整堆的结构将堆顶元素置于正确的位置上
四.基于数组实现大顶堆
package 堆;
import java.util.Arrays;
import java.util.Iterator;
/**
* 大顶堆
*/
public class MaxHeap implements Iterable<Integer>{
int[] array;
int size;
/**
* 通过构造方法将任意数组调整为大顶堆
* @param array
*/
public MaxHeap(int[] array){
this.array = array;
this.size = array.length;
this.heapify();
}
public MaxHeap(int capacity){
this.array = new int[capacity+1];
size = 0;
}
/**
* 调整堆
* 从最后一个非叶子节点开始，以此向前开始调整堆
* 使其符合大顶堆的特性
*/
public void heapify(){
for (int i = size/2 -1 ; i>=0 ; i--) {
down(i);
}
}
/**
* 添加元素，
* 1.先添加到数组的末尾+1处 size处
* 2.然后判断该处和他的父节点处元素大小，如果比他的父亲大，就交换二者，
* parent = (child-1) / 2
* 3.然后将child置为parent，parent置为它的parent，以此往上走，
* 4.两种情况:
* - (1)直到child为 0，这种是offered比所有的元素都大的情况
* - (2)直到child处元素不比parent处大，就是已经上浮到合适的位置了，
* 退出循环
* 5.将array[child]处赋值为offered
*
* @param offered
* @return
*/
public boolean offer(int offered){
if(size == array.length){
return false;
}
//上浮
size++;
up(offered);
return true;
}
/**
* 上浮
* @param offered
*/
public void up(int offered){
//先找到末尾位置
int child = size;
//如果child>0,就继续上浮
while (child > 0){
//找到父节点
int parent = (child - 1) / 2;
//比较child和parent
if(offered > array[parent]){
//交换child和parent
array[child] = array[parent];
}else {
break;
}
//交换完成一次之后，将child置为parent
child = parent;
}
//上浮完成后，为array[child]处赋值
array[child] = offered;
}
/**
* 获取堆顶元素
* @return 堆顶元素
*/
public int peek(){
if(size==0){
return Integer.parseInt(null);
}
return array[0];
}
/**
* 移除堆顶元素
* @return 堆顶元素
*/
public int poll(){
if(size==0){
return Integer.parseInt(null);
}
int top = array[0];
//先交换堆顶和最后一个元素
swap(0,size-1);
size--;
//从堆顶开始下潜
down(0);
return top;
}
/**
* 移除指定位置处的元素
* @param index 指定位置
* @return index处元素
*/
public int poll(int index){
if(size==0){
return Integer.parseInt(null);
}
int indexE = array[index];
//先交换index处和最后一个元素
swap(index,size-1);
size--;
//从index处开始下潜
down(index);
return indexE;
}
/**
* 替换堆顶元素
*/
public void replace(int replaced){
if(size==0){
throw new RuntimeException("堆为空！");
}
array[0] = replaced;
//下潜
down(0);
}
/**
* 下潜操作
* @param parent 最后一个非叶子节点
*/
public void down(int parent){
//找到该非叶子节点的左孩子和右孩子
int left = parent*2 + 1;
int right = left + 1;
//先假设parent是最大的
int max = parent;
//然后分别比较parent和left,right的大小
if(left<size && array[max] < array[left]){
max = left;
}
if(right<size && array[max] < array[right]){
max = right;
}
/**
* 如果max!=parent，说明孩子有比父亲大的，所以要交换二者，
* 当交换后，堆结构可能会被破坏，所以要继续调整堆，使其所有节点
* 都满足大顶堆的特性
*/
if(max != parent){
swap(max,parent);
down(max);
}
}
public void swap(int i,int j){
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
@Override
public Iterator<Integer> iterator() {
return new Iterator<Integer>() {
int p = 0;
@Override
public boolean hasNext() {
return p != size;
}
@Override
public Integer next() {
int res = array[p];
p++;
return res;
}
};
}
}
测试一下：
public static void main(String[] args) {
int[] array = {1,2,3,4,5,6,7};
MaxHeap maxHeap = new MaxHeap(array);
System.out.println(Arrays.toString(maxHeap.array));
maxHeap.poll();
System.out.print("[");
for (Integer num : maxHeap) {
System.out.print(num+",");
}
System.out.print("]");
}运行：
[7, 5, 6, 4, 2, 1, 3]
[6,5,3,4,2,1,]
进程已结束,退出代码0可以看到满足大顶堆特性
五.堆排序
可以利用大顶堆的特性，堆顶元素最大，实现堆排序，将无序数组调整为从小到大排序
/**
* 堆排序
*/
@Test
public void testHeapPaiXu(){
int[] array = {3,1,6,2,7,4,9,1,3};
MaxHeap heap = new MaxHeap(array);
while (heap.size > 1){
//先交换
heap.swap(0,heap.size-1);
//size减一
heap.size--;
//下潜调整堆
heap.down(0);
}
System.out.println(Arrays.toString(heap.array));
}运行：
[1, 1, 2, 3, 3, 4, 6, 7, 9]可以看到已经成功调整了排序
六.小顶堆
小顶堆（Min Heap）是一种堆的实现方式，它满足以下性质：
- 每个节点的值都小于或等于其子节点的值。
- 堆顶元素（根节点）是整个堆中最小的元素。
在小顶堆中，任意节点的值都小于或等于其子节点的值，但是它们之间的顺序并没有固定的要求，即左右子节点之间的大小关系并不要求一定是有序的。
小顶堆可以通过数组或完全二叉树来实现。在数组中，堆的根节点存储在索引为0的位置，而任意节点i的左子节点存储在索引为2i+1的位置，右子节点存储在索引为2i+2的位置。
小顶堆的常见操作包括：
- 插入元素：将元素插入堆的底部，然后通过调整堆的结构将其置于正确的位置上，以保持堆的性质。
- 删除堆顶元素：将堆顶元素与堆底元素交换，然后删除堆底元素，再通过调整堆的结构将堆顶元素置于正确的位置上。
小顶堆在各种算法和数据结构中也有广泛应用，和大顶堆类似。
七.基于数组实现小顶堆
实现小顶堆和大顶堆类似，只需要把up和down中的比较符合改变即可:
package 堆;
import java.util.Iterator;
/**
* 小顶堆
*/
public class MinHeap implements Iterable<Integer> {
int[] array;
int size;
/**
* 通过构造方法将任意数组调整为大顶堆
* @param array
*/
public MinHeap(int[] array){
this.array = array;
this.size = array.length;
this.heapify();
}
public MinHeap(int capacity){
this.array = new int[capacity+1];
this.size = 0;
}
/**
* 调整堆
* 从最后一个非叶子节点开始，以此向前开始调整堆
* 使其符合大顶堆的特性
*/
public void heapify(){
for (int i = size/2 -1 ; i>=0 ; i--) {
down(i);
}
}
/**
* 添加元素，
* 1.先添加到数组的末尾+1处 size处
* 2.然后判断该处和他的父节点处元素大小，如果比他的父亲小，就交换二者，
* parent = (child-1) / 2
* 3.然后将child置为parent，parent置为它的parent，以此往上走，
* 4.两种情况:
* - (1)直到child为 0，这种是offered比所有的元素都小的情况
* - (2)直到child处元素不比parent处小，就是已经上浮到合适的位置了，
* 退出循环
* 5.将array[child]处赋值为offered
*
* @param offered
* @return
*/
public boolean offer(int offered){
if(size == array.length){
return false;
}
//上浮
size++;
up(offered);
return true;
}
/**
* 上浮
* @param offered
*/
public void up(int offered){
//先找到末尾位置
int child = size;
//如果child>0,就继续上浮
while (child > 0){
//找到父节点
int parent = (child - 1) / 2;
//比较child和parent
if(offered < array[parent]){
//交换child和parent
array[child] = array[parent];
}else {
break;
}
//交换完成一次之后，将child置为parent
child = parent;
}
//上浮完成后，为array[child]处赋值
array[child] = offered;
}
/**
* 获取堆顶元素
* @return 堆顶元素
*/
public int peek(){
if(size==0){
return Integer.parseInt(null);
}
return array[0];
}
/**
* 移除堆顶元素
* @return 堆顶元素
*/
public int poll(){
if(size==0){
return Integer.parseInt(null);
}
int top = array[0];
//先交换堆顶和最后一个元素
swap(0,size-1);
size--;
//从堆顶开始下潜
down(0);
return top;
}
/**
* 移除指定位置处的元素
* @param index 指定位置
* @return index处元素
*/
public int poll(int index){
if(size==0){
return Integer.parseInt(null);
}
int indexE = array[index];
//先交换index处和最后一个元素
swap(index,size-1);
size--;
//从index处开始下潜
down(index);
return indexE;
}
/**
* 替换堆顶元素
*/
public void replace(int replaced){
if(size==0){
throw new RuntimeException("堆为空！");
}
array[0] = replaced;
//下潜
down(0);
}
/**
* 下潜操作
* @param parent 最后一个非叶子节点
*/
public void down(int parent){
//找到该非叶子节点的左孩子和右孩子
int left = parent*2 + 1;
int right = left + 1;
//先假设parent是最大的
int min = parent;
//然后分别比较parent和left,right的大小
if(left<size && array[min] > array[left]){
min = left;
}
if(right<size && array[min] > array[right]){
min = right;
}
/**
* 如果min!=parent，说明孩子有比父亲小的，所以要交换二者，
* 当交换后，堆结构可能会被破坏，所以要继续调整堆，使其所有节点
* 都满足小顶堆的特性
*/
if(min != parent){
swap(min,parent);
down(min);
}
}
public void swap(int i,int j){
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
@Override
public Iterator<Integer> iterator() {
return new Iterator<Integer>() {
int p = 0;
@Override
public boolean hasNext() {
return p != size;
}
@Override
public Integer next() {
int res = array[p];
p++;
return res;
}
};
}
}
八.ProiorityQueue和Heap
Java中自带的堆实现类包括PriorityQueue和Heap，它们都是基于小顶堆的数据结构。
-
PriorityQueue: PriorityQueue是Java中的优先队列类，它是通过小顶堆实现的。PriorityQueue可以自动将元素按照优先级进行排序，并保证每次操作的时间复杂度为O(logn)。
PriorityQueue的常见方法包括：add(E e)、offer(E e)：将元素插入队列；remove()、poll()：删除并返回队列中的头元素；peek()：返回队列中的头元素。 -
Heap：Heap是Java中提供的用于实现堆数据结构的抽象类，它定义了一些基本的堆操作，如插入、删除元素，获取堆顶元素等。可以通过继承Heap类来实现自定义的堆。
示例：
1.PriorityQueue的例子：
import java.util.PriorityQueue;
public class PriorityQueueExample {
public static void main(String[] args) {
// 创建一个优先队列，默认是小顶堆
PriorityQueue<Integer> pq = new PriorityQueue<>();
// 使用offer方法插入元素到队列中
pq.offer(5);
pq.offer(3);
pq.offer(8);
pq.offer(1);
pq.offer(9);
// 使用poll方法获取并删除队列中的头元素
while (!pq.isEmpty()) {
System.out.print(pq.poll() + " ");
}
}
}输出结果：1 3 5 8 9
2.Heap的例子：
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
public class HeapExample {
public static void main(String[] args) {
// 创建一个堆
List<Integer> heap = new Heap<>(Comparator.naturalOrder());
// 使用offer方法插入元素到堆中
heap.offer(5);
heap.offer(3);
heap.offer(8);
heap.offer(1);
heap.offer(9);
// 使用poll方法获取并删除堆顶元素
while (!heap.isEmpty()) {
System.out.print(heap.poll() + " ");
}
}
}输出结果：1 3 5 8 9
请注意，Heap类并不是Java标准库中的一部分，它只是一个示例实现。在实际开发中，通常会使用PriorityQueue来实现堆的功能
九.求数组中第K大元素
package 堆;
/**
* 求数组中第k大的元素
*/
public class L255_K_max {
public static void main(String[] args) {
int[] array = {1,4,2,6,3,9,5,10};
int max = K_Max(array, 2);
System.out.println(max);
}
/**
* 思路：
* 1.首先将前 k 个元素添加到堆中，调整为小顶堆
* 2.然后从 k 处向后依次遍历：
* ->（1）如果 元素比堆顶元素小，就跳过
* -> (2) 如果元素比堆顶元素大，则替换堆顶元素
* 3.最后遍历完成，返回堆顶元素，该元素就是第 K 大的元素
* @param array
* @param k
* @return
*/
public static int K_Max(int[] array,int k){
MinHeap heap = new MinHeap(k);
for (int i = 0; i < k; i++) {
heap.offer(array[i]);
}
for(int i = k; i< array.length;i++){
if(array[i] > heap.peek()){
heap.replace(array[i]);
}
}
return heap.peek();
}
}
运行:
9
进程已结束,退出代码0十.求数据流中第K大元素
package 堆;
/**
* 求数据流中第K大的元素
*/
public class L703_Stream_K_Max {
private MinHeap heap;
public L703_Stream_K_Max(int[] nums,int k){
this.heap = new MinHeap(k);
for (int num : nums) {
add(num);
}
}
public int add(int val){
//如果不满，先添加
if(heap.size != heap.array.length-1){
heap.offer(val);
}else if( val > heap.peek() ){
//满了，替换返回
heap.replace(val);
}
return heap.peek();
}
public static void main(String[] args) {
int nums[] = {1,2,6,3,11,5,9};
L703_Stream_K_Max stream_k_max = new L703_Stream_K_Max(nums, 3);
System.out.println(stream_k_max.add(2));
System.out.println(stream_k_max.add(12));
System.out.println(stream_k_max.add(1));
}
}
运行:
5
9
9
进程已结束,退出代码0十一.求数据流的中位数
/**
* 求数据流的中位数
*/
public class L295_Stream_Medin {
/**
* 实现思路：
* 比如现在有一个数组: [1,2,3,4,5,6,7,8]
* 那么它的中位数是 （4+5）/2 = 4.5
* 如果是：[1,2,3,4,5,6,7,8,9]
* 那么中位数是 5
* 一般情况下，每次都先排序，然后找到中位数，这样效率不高，
*
* 堆实现:
* 将数组元素平均分为两份，左边和右边，然后两边分别建堆
* left 建立 MaxHeap, right 建立 MinHeap
* 左边的堆顶是左边最大的，右边的堆顶是右边最小的，
* 这样，相加除以 2 就可以得到，
* 如果是奇数，只需要取左边的堆顶元素
*
* 向数组中添加元素时：
* 1.如果两边元素个数一样，向左边添加元素,
* 2.如果两边个数不一样(左边比右边多一),向右边添加元素
* 注意：添加元素是有技巧的：
* -》向左边添加元素时，先向右边添加元素，然后挤出右边最小的一个元素添加到左边
* -》向右边添加元素时，先向左边添加元素，然后挤出左边最大的一个元素添加到右边
*/
private MaxHeap leftMaxHeap = new MaxHeap(10);
private MinHeap rightMinHeap = new MinHeap(10);
public void add(int num){
//如果左右两边个数相等
if(leftMaxHeap.size == rightMinHeap.size){
/**
* 添加到左边去，但是要先向右添加，再挤出一个最小的到左边
*/
rightMinHeap.offer(num);
leftMaxHeap.offer(rightMinHeap.poll());
}else {
//左边比右边多一个，同理，先向左添加，然后挤出一个最大的到右边
leftMaxHeap.offer(num);
rightMinHeap.offer(leftMaxHeap.poll());
}
}
/**
* 返回中位数
* @return
*/
public double getMedNum(){
//如果两边个数一样，返回二者堆顶元素平均值
if(leftMaxHeap.size == rightMinHeap.size){
return (leftMaxHeap.peek() + rightMinHeap.peek()) / 2.0;
}else{
//返回左边元素
return leftMaxHeap.peek();
}
}
public static void main(String[] args) {
L295_Stream_Medin stream_medin = new L295_Stream_Medin();
stream_medin.add(1);
stream_medin.add(2);
stream_medin.add(3);
stream_medin.add(4);
stream_medin.add(5);
stream_medin.add(6);
stream_medin.add(7);
stream_medin.add(8);
stream_medin.add(9);
System.out.println(stream_medin.getMedNum());
}
}运行：
5.0
进程已结束,退出代码0