文章目录
堆
堆的定义
堆是计算机科学中一类特殊的数据结构的统称，堆通常可以被看做是一棵完全二叉树的数组对象。
堆的特性
1.它是完全二叉树
- 它是完全二叉树，除了树的最后一层结点不需要是满的，其它的每一层从左到右都是满的，如果最后一层结点不是满的，那么要求左满右不满。
2.它通常用数组来实现
- 具体方法就是将二叉树的结点按照层级顺序放入数组中，根结点在位置1，它的子结点在位置2和3，而子结点的子结点则分别在位置4,5,6和7，以此类推。
- 如果一个结点的位置为k，则它的父结点的位置为[k/2],而它的两个子结点的位置则分别为2k和2k+1。
- 这样，在不使用指针的情况下，我们也可以通过计算数组的索引在树中上下移动：从a[k]向上一层，就令k等于k/2,向下一层就令k等于2k或2k+1。
3.每个结点都大于等于它的两个子结点
- 这里要注意堆中仅仅规定了每个结点大于等于它的两个子结点，但这两个子结点的顺序并没有做规定，跟我们之前学习的二叉查找树是有区别的。
堆的实现
堆的API设计
1. 基础方法实现:
public class Heap<T extends Comparable<T>> {
//存储堆中的元素
private T[] items;
//记录堆中元素的个数
private int N;
public Heap(int capacity) {
this.items= (T[]) new Comparable[capacity+1];
this.N=0;
}
//判断堆中索引i处的元素是否小于索引j处的元素
private boolean less(int i,int j){
return items[i].compareTo(items[j])<0;
}
//交换堆中i索引和j索引处的值
private void exch(int i,int j){
T temp = items[i];
items[i] = items[j];
items[j] = temp;
}
}
2. insert插入方法的实现
- 堆是用数组完成数据元素的存储的，由于数组的底层是一串连续的内存地址，所以我们要往堆中插入数据，我们只能往数组中从索引0处开始，依次往后存放数据，
- 但是堆中对元素的顺序是有要求的，每一个结点的数据要大于等于它的两个子结点的数据，所以每次插入一个元素，都会使得堆中的数据顺序变乱，这个时候我们就需要通过一些方法让刚才插入的这个数据放入到合适的位置。
上浮算法swim()
所以，如果往堆中新插入元素，我们只需要不断的比较新结点a[k]和它的父结点a[k/2]的大小，然后根据结果完成数据元素的交换，就可以完成堆的有序调整。
//往堆中插入一个元素
public void insert(T t){
items[++N]=t;
swim(N);
}
//使用上浮算法，使索引k处的元素能在堆中处于一个正确的位置
private void swim(int k){
//通过循环，不断的比较当前结点的值和其父结点的值，如果发现父结点的值比当前结点的值小，则交换位置
while(k>1){
//比较当前结点和其父结点
if (less(k/2,k)){
exch(k/2,k);
}
k = k/2;
}
}
3. delMax删除最大元素方法的实现
- 由堆的特性我们可以知道，索引1处的元素，也就是根结点就是最大的元素，当我们把根结点的元素删除后，需要有一个新的根结点出现，这时我们可以暂时把堆中最后一个元素放到索引1处，充当根结点，但是它有可能不满足堆的有序性需求，这个时候我们就需要通过一些方法，让这个新的根结点放入到合适的位置。
下沉算法sink()
- 所以，当删除掉最大元素后，只需要将最后一个元素放到索引1处，并不断的拿着当前结点a[k]与它的子结点a[2k]和a[2k+1]中的较大者交换位置，即可完成堆的有序调整。
//删除堆中最大的元素,并返回这个最大元素
public T delMax(){
T max = items[1];
//交换索引1处的元素和最大索引处的元素，让完全二叉树中最右侧的元素变为临时根结点
exch(1,N);
//最大索引处的元素删除掉
items[N]=null;
//元素个数-1
N--;
//通过下沉调整堆，让堆重新有序
sink(1);
return max;
}
//使用下沉算法，使索引k处的元素能在堆中处于一个正确的位置
private void sink(int k){
//通过循环不断的对比当前k结点和其左子结点2*k以及右子结点2k+1处中的较大值的元素大小，如果当前结点小，则需要交换位置
while(2*k<=N){
//获取当前结点的子结点中的较大结点
int max;//记录较大结点所在的索引
if (2*k+1<=N){
if (less(2*k,2*k+1)){
max=2*k+1;
}else{
max=2*k;
}
}else {
max = 2*k;
}
//比较当前结点和较大结点的值
if (!less(k,max)){
break;
}
//交换k索引处的值和max索引处的值
exch(k,max);
//变换k的值
k = max;
}
}
堆的实现代码
public class Heap<T extends Comparable<T>> {
//存储堆中的元素
private T[] items;
//记录堆中元素的个数
private int N;
public Heap(int capacity) {
this.items= (T[]) new Comparable[capacity+1];
this.N=0;
}
//判断堆中索引i处的元素是否小于索引j处的元素
private boolean less(int i,int j){
return items[i].compareTo(items[j])<0;
}
//交换堆中i索引和j索引处的值
private void exch(int i,int j){
T temp = items[i];
items[i] = items[j];
items[j] = temp;
}
//往堆中插入一个元素
public void insert(T t){
items[++N]=t;
swim(N);
}
//使用上浮算法，使索引k处的元素能在堆中处于一个正确的位置
private void swim(int k){
//通过循环，不断的比较当前结点的值和其父结点的值，如果发现父结点的值比当前结点的值小，则交换位置
while(k>1){
//比较当前结点和其父结点
if (less(k/2,k)){
exch(k/2,k);
}
k = k/2;
}
}
//删除堆中最大的元素,并返回这个最大元素
public T delMax(){
T max = items[1];
//交换索引1处的元素和最大索引处的元素，让完全二叉树中最右侧的元素变为临时根结点
exch(1,N);
//最大索引处的元素删除掉
items[N]=null;
//元素个数-1
N--;
//通过下沉调整堆，让堆重新有序
sink(1);
return max;
}
//使用下沉算法，使索引k处的元素能在堆中处于一个正确的位置
private void sink(int k){
//通过循环不断的对比当前k结点和其左子结点2*k以及右子结点2k+1处中的较大值的元素大小，如果当前结点小，则需要交换位置
while(2*k<=N){
//获取当前结点的子结点中的较大结点
int max;//记录较大结点所在的索引
if (2*k+1<=N){
if (less(2*k,2*k+1)){
max=2*k+1;
}else{
max=2*k;
}
}else {
max = 2*k;
}
//比较当前结点和较大结点的值
if (!less(k,max)){
break;
}
//交换k索引处的值和max索引处的值
exch(k,max);
//变换k的值
k = max;
}
}
}
测试
public class HeapTest {
public static void main(String[] args) {
//创建堆对象
Heap<String> heap = new Heap<>(10);
//往堆中存入字符串数据
heap.insert("A");
heap.insert("B");
heap.insert("C");
heap.insert("D");
heap.insert("E");
heap.insert("F");
heap.insert("G");
//通过循环从堆中删除数据
String result = null;
while((result = heap.delMax())!=null){
System.out.print(result+" ");
}
}
}
