文章目录
堆上浮下浮代码堆排序堆应用
堆
堆不算是一种数据结构,只是一类数据结构的统称,通常用完全二叉树来实现堆.完全二叉树即除了叶子节点外,必须存在左右孩子节点的树.不完全二叉树是除了叶子节点外,存在一个或多个节不完全存在左右孩子节点.在前面小编提到过一笔,树不一定要用向链表那样的结构去实现的,我们完全可以用数组,用数组的好处是,可以快速遍历,根据某个节点,我们可以快速获取其父节点或者子节点,请看下图数组存储树的结构:如果一个节点的位置是k,那么其父节点的位置是k/2,其左子节点为k/2,右子节点为k/2+1.其次,树的根节点一定要大于左右子节点,但左右子节点存储没有规定.
上浮
上浮这个概念发生在往堆里放入一个元素的时候,因为我们是用数组存储堆元素的,所以当我们往堆里放入一个元素的时候,只能是往数组的最后一位放置,但放入的元素是不能确保符合堆规则的,也就是上一层父节点必须比左右子节点的任何值都大,这个时候就要调整堆,称之为上浮:请看上图,如果要插入字母S,只能放入数组的最后一个元素的后一位,根据二叉树和数组位置的对应,该节点只能是H的右子节点.但是S是比H大的(按照字母顺序),所以要上浮,与H交换位置,交换后,又发现P比S要小,继续与P交换位置,直到发现其上一层父节点比自己大,就停止交换.
下浮
下浮就刚好和上浮相反过来,也就是当要删除根节点T的时候,我们要选出一个节点当根节点,这里其实有一个很巧妙的算法,就是将根节点与最后一个节点交换位置,然后再让根节点指向null,这个时候原来处于最后位置的节点就成了根节点,但这个根节点是不符合堆规则的,有可能比左右子节点要小,所以要下沉:请看上面这张图,原本T是在根节点的,因为我们要删除T,所以与原本在最后一个节点的G删除,那么就先交换位置,然后直接删除T,这个时候G成为了根节点,而不符合堆规则,所以要调整堆,要下浮:
下浮要唯一绕不过来的一点是到底往左节点下浮还是右节点下浮,其实都有可能,只是要往子节点中最大的那一个节点下浮?为什么不是最小的呢?因为如果我们与最小的交换了,那个这个最小的成为了根节点,它比右节点又小了,因为本来就比右节点要小.而往最大的那一个子节点下浮,目的是为了与该子节点交换后,该子节点作为根节点,仍然比其本身的子节点都要大,才符合堆的规则.
代码
package com.hyb.ds.堆;
public class Heap
private T[] items;
private int n;
public Heap(int cap){
//因为T继承了Comparable,所以要new这个,而不是Object
//从1开始
// this.items= (T[]) new Object[cap+1];
this.items=(T[])new Comparable[cap+1];
this.n=0;
}
//比较两个位置的大小
public boolean less(int i,int j){
return items[i].compareTo(items[j])<0;
}
public void swap(int i,int j){
T t=items[i];
items[i]=items[j];
items[j]=t;
}
//往堆里插入一个元素,从1开始
public void insert(T t){
items[++n]=t;
swim(n);
}
//上浮调整堆
public void swim(int k){
while (k>1){
//如果父节点比当前节点小
if (less(k/2,k)){
//交换节点
swap(k/2,k);
k=k/2;
}else break;
//将位置调整
}
}
//删除堆最大的元素
public T delMax(){
T max=items[1];
//最根节点为最大节点
//交换最大节点和最后一个节点
swap(1,n);
//删除最大节点
items[n]=null;
//n--
n--;
//让根节点下沉
sink(1);
return max;
}
//让根节点下沉
public void sink(int index){
while ((2*index+1)<=n){
int maxChild;
if (less(2*index,2*index+1))
maxChild=2*index+1;
else
maxChild=2*index;
if (less(maxChild,index))
break;
swap(maxChild,index);
index=maxChild;
}
}
public static void main(String[] args) {
Heap
stringHeap.insert("A");
stringHeap.insert("B");
stringHeap.insert("C");
stringHeap.insert("D");
stringHeap.insert("E");
stringHeap.insert("F");
stringHeap.insert("G");
String result=null;
while ((result=stringHeap.delMax())!=null){
System.out.println(result);
}
}
}
堆排序
这是八大排序算法的最后一个排序算法,堆是存在数组里的,所以可以利用堆的特性对数组进行排序.前面小编讲过,根节点是一定要大于左右子节点的,所以我们在删除的时候进行输出,是可以从大到小进行输出的.接下来我们对上图进行一个排序,从小到大,依次顺序应该是A->G我们只需要将A与G进行调换,这样子G就到达了数组最高的位置,因为G是最大的,所以到了最后.此刻A处于根节点,破坏了堆规则,所以需要调整堆,需要将A下沉,.之后继续将根节点与数组位置最后一个节点交换,注意,这最后一个节点是B,因为A所在的位置已经交换过,不能再交换了.
有了这个思想后,接下来小编做一个测试,将数组转化为堆,然后将堆进行一个从小到大的排序:
//根据范围下沉
public void sink(int index,int range){
while (2*index+1<=range){
//判断当前节点中较大的子节点
int max;
if (less(2*index,2*index+1)){
max=2*index+1;
}else max=2*index;
//将当前节点与最大子节点比较
if (less(max,index)){
break;
}
swap(index,max);
index=max;
}
}
//根据传过来的数组,生成堆
public void ArrayHeap(T[] heap){
//先将所有元素拷贝进堆里
System.arraycopy(heap,0,items,1,heap.length);
//然后要对元素进行下沉,这里是从长度的1/2开始,因为剩余的都是叶子节点
for (int i=heap.length/2;i>0;i--){
//下沉
sink(i,heap.length-1);
}
}
//堆排序
public void heapSort(T[] heap){
ArrayHeap(heap);
//标记与根节点交换的最后一个节点位置
int last=heap.length;
while (last!=1){
//交换头节点与尾结点
swap(1,last);
//让last改变
last--;
//让头节点下沉
sink(1,last);
}
//将heap中的数据再复制过去
System.arraycopy(items,1,heap,0,heap.length);
}
public static void main(String[] args) {
Heap
// stringHeap.insert("A");
// stringHeap.insert("B");
// stringHeap.insert("C");
// stringHeap.insert("D");
// stringHeap.insert("E");
// stringHeap.insert("F");
// stringHeap.insert("G");
// String result=null;
// while ((result=stringHeap.delMax())!=null){
// System.out.println(result);
// }
String[] a=new String[]{"G","F","E","D","C","B","A"};
stringHeap.heapSort(a);
for (String s :
a) {
System.out.println(s);
}
}
堆应用
从堆的性质上可以看,堆是可以实现成优先级队列的,因为我们知道堆的根节点是一定会大于左右子节点的,这就很方便的存放优先级队列,当我们需要将优先级最高的元素取出的时候,直接取出根节点就可以了.堆应用中一个应用便是索引队列,在正常的堆里,元素是无序的,我们只能取得其最大值或者最小值,而中间的值是无法取得的,所以我们将元素存放在数组里去实现堆.这样就可以从下标快速获取得到对应的值:
但这样又会存在一个问题,如果我们调换了某两个索引位置的值,那么就要调整堆,这个时候原本值就不是在最开始那个位置了,就导致了最后还是无序的,无法根据最开始的位置获取值.为了解决这个问题,我们使用一个辅助树来解决问题,这个辅助树用来存放我们堆里各个值的索引:这个辅助树的值就是原数组的索引,那么如果原数组要进行堆调整,就可以直接调整辅助树就行了,这样子无论辅助树的值调整去怎样的位置,它的值都是不变的,根据这个值,就可以得到原数组的值.但是,还有一个问题: 如果原数组的值改变了,虽然说,该值的索引没有改变,但是你在调整堆的时候,就要去辅助树里找到原值索引对应的位置,比如说,这里原数组改变了索引0的值s为H,那么这个时候就要去调整堆,根据H的索引0,找到辅助树里的值为0的位置去进行调整.这样子看似不影响原数组值的位置,但是效率低啊,因为你要找到这个0的话,就要遍历辅助树,因为在辅助树里这个0是值,不是索引.而如果辅助树很大,那么查询效率是很低的,这样子我们通过空间换时间这个手段就得不偿失.所以,我们又要去保存一份辅助树,暂且叫它为2号,前一个辅助树是1号.那么这个2号里的值就保存1号的索引,而2号本身的索引就会和原数组的索引重合:所以你看,如果修改了S的值为H,那么这个时候,可以拿到该值的索引0,最直接去2号寻找对应的值,这个值,就是我们在一号里的索引,就可以直接根据这个索引去调整2号堆了.
文章来源
发表评论