堆的相关概念
一、堆的概念
- 从结构上看，堆是一棵完全二叉树（与满二叉树相比仅缺少一部分右分支）
- 在实现过程中采用数组作为基础存储结构，在实际应用中通常会基于动态数组来管理元素数量的变化（为了高效管理元素数量的变化）。这种存储方式具有以下特点：内存增长较为高效且资源利用率较高；通过层序遍历的方式将完全二叉树有序地存储于动态数组中
- 堆根据根节点的大小值可分为大根堆和小根堆两种类型
二、大根堆 即整个完全二叉树结构，在这种数据组织形式中\dots 每个节点的数值均大于其左右子树的所有数值
这即为一种大根堆，在其中所有父节点（Root）的数值均大于其子节点（Child）的数量。由此可知，在整个堆中的根节点其数值为该堆的最大值。值得注意的是，并非所有非父子关系的节点之间都存在数值上的直接联系——只要保证每个父节点的数值大于其子节点即可。
三、小根堆 完全二叉树的小根堆表示，在完全二叉树中每个父节点都具有较小的关键字值相对于其左右子树的所有节点值。
此乃一个基本的小根堆其定义类似于大根堆只不过其根节点的数值小于左右子节点数值同时此关系并非必然存在于各层次之间
我们可以将队列元素存储在完全二叉树结构中，并以数组形式表示整个队列中的数值。为了构建一个大根堆或小根堆，我们需要将给定的一个无序数组进行转换。在实现过程中，我们首先对原始数据进行循环遍历，并逐个将其添加到初始空的树结构中。每次添加后会通过上浮操作确保局部结构满足最大或最小条件。具体而言，在每一次插入操作完成后（即上浮操作），如果新插入的元素大于当前节点，则继续上浮比较；如果当前节点已经是最大的（对于大根堆）或者最小的（对于小根堆），则说明整个树已经满足条件并完成本次插入。例如，在构建最大值优先的大根堆时，在处理数据序列[2, 6, 3, 4, 1]时，在完成所有插入和调整之后最终得到了[6, 4, 3, 2, 1]的最大值排列结果。
从图中大致可以看出整个流程如下：首先将该元素放置在堆的最后一端位置，并随后与其直接相邻的父节点展开对比关系。如果该值大于当前节点，则需执行上浮操作并与其父节点交换数值位置。持续地与其父节点进行比较直到满足条件或者抵达堆顶位置为止，在此状态下完成一个元素的添加操作并将整个结构转化为最大堆形式。经过对所有数组元素依次处理后即可形成完整的最大堆结构。
下面我们用代码来实现一下主要步骤：
import java.util.ArrayList;
import java.util.List;
import java.util.NoSuchElementException;
public class MaxHeap {
private List<Integer> data;
//构造函数
public MaxHeap(int count){
//我们通过动态数组来实现
this.data = new ArrayList<>(count);
}
public MaxHeap(){
this(10);
}
//根据下标找到父节点的下标
private int parent(int i){
return (i-1) >> 1;
}
//根据下标找到当前节点的左子树下标
private int leftChild(int i){
return (i << 1) + 1;
}
//根据下标找到当前节点的右子树下标
private int rightChild(int i){
return (i << 1) + 2;
}
/** * 添加操作
* @param val
*/
public void add(int val){
this.data.add(val);
siftUp(data.size()-1);
}
//上浮
private void siftUp(int i) {
//当该元素到最顶端或它的值不大于当前根节点的值的时候表示上浮完成
while (i > 0 && data.get(i) > data.get(parent(i)))
{
//保存房钱父节点的下标
int parent = parent(i);
//进行交换
swap(i,parent);
//再将要进行判断的下标更新后继续循环判断
i = parent;
}
}
//交换操作
private void swap(int i, int parent) {
int temp = data.get(i);
data.set(i, data.get(parent));
data.set(parent,temp);
}
//取出当前最大堆的最大元素并返回最大的元素
//同时将推重新排列
public int extractMax(){
if(data.size() == 0)
{
throw new NoSuchElementException("this heap is null!");
}
//最大堆的堆顶是最大的
int max = data.get(0);
//堆的最后一个元素
int last = data.get(data.size() - 1);
//把最后一个元素放到堆顶
data.set(0, last);
//最后一个元素放上去之后把最后的这个删掉
data.remove(data.size() - 1);
//从堆顶开始下沉，重新将堆变成堆
siftDown(0);
return max;
}
//覆写toString方法
@Override
public String toString() {
return data.toString();
}
public static void main(String[] args) {
int[] data = {17,90,68,12,15,14,70,30,20};
MaxHeap heap = new MaxHeap(data.length);
for (int i = 0 ; i< data.length ; i++)
{
heap.add(data[i]);
}
System.out.println(heap);
}
}结果：
