带有优先级的完全二叉树-堆

堆的概念

堆是一种完全二叉树(除了最后一层每个节点的子节点都是满的,最后一层的节点也是集中在左边)

虽然堆是一棵二叉树,但也由于它是一棵完全二叉树的原因,可以使用一个数组来表示堆。(层次遍历)

我们常用到的堆是最大堆和最小堆

最小堆

最小堆要求,对于任意一个父结点来说,其子结点的值都大于这个父节点。

带有优先级的完全二叉树-堆

对于这个最小堆,可以用数组表示为[1,3,30,22,10,50]

最大堆

最大堆和最小堆相反,对于任意一个父结点来说,其子结点的值都小于这个父节点。

堆的操作

插入

我们看如何构建一个最小堆:

对于[30,15,5,11,22,2]

最小堆的构建过程

可以看出,我们依次按数组的顺序放入二叉树的节点,一旦出现子节点比父节点的值小,交换子节点和父节点。

我们称这个操作为向上堆化,堆化后的数组为[2,11,5,30,22,15]

删除

将堆树中待删除的节点A与堆树中的最后一个节点B互换,然后调整节点B到合适的位置,最后从堆树中删除排在堆数组最后的节点A。

不过在堆这个数据结构中,我们通常只需要删除堆顶元素。

删除堆顶元素

向下堆化

堆的应用

优先级队列

实现优先级队列的方法有很多,但是用堆来实现是最直接、最高效的。堆和优先级队列非常相似,一个堆就可以看作一个优先级队列。从优先级队列中取出优先级最高的元素,就相当于取出堆顶元素。

堆排序

堆排序实际上就是不断获取堆顶元素。

对于最大堆来说,我们知道最大堆的队首元素是整个堆最大的元素,当我们删除并得到堆顶元素时,剩下的元素会重新堆化,得到一个新的堆顶元素,这样不断删除并获取堆顶元素,最终拿到的就是一个从大到小的有序序列。

当然,用数组代表堆,我们在排序的时候可以不必删除元素,只需要将原堆顶元素移动到数组末尾,将剩下的元素重新堆化,然后重复该步骤,最后就能得到一个从小到大排序的数组。

附:代码示例

实现一个完整的最大堆并堆排序一个数组

public class MaxHeap {
    private int[] heap;
    private int size;

    // 用数组来初始化一个堆
    public MaxHeap(int[] source){
        heap = source;
        size = source.length;
        heapify();
    }

    public int get(int index){
        return heap[index];
    }

    public int size() {
        return size;
    }
    //移除一个元素,并从这个元素开始向下堆化
    public int removeAt(int index){
        int node = heap[index];
        swap(index,size-1);
        size--;
        downShift(index);
        return node;
    }

    //构建堆
    public void heapify(){
        for(int i = 0; i < size; i++){
            int position = i;
            upShift(position);
        }
    }

    //向上堆化
    public void upShift(int position){
        int parent = getParent(position);
        while (position>0 && (heap[position]>heap[parent])){
            swap(position,parent);
            position = parent;
            parent = getParent(position);
        }
    }

    //向下堆化
    public void downShift(int position){
        int children1 = position*2+1;
        int children2 = position*2+2;
        while (children1<size){
            int toSwap = children1;
            if(children2<size){
                toSwap = heap[children1]>heap[children2]?children1:children2;
            }
            if(heap[toSwap]>heap[position]){
                swap(position,toSwap);
                position = toSwap;
                children1 = position*2+1;
                children2 = position*2+2;
            }else break;
        }
    }

    public void swap(int source,int destination){
        int cache = heap[source];
        heap[source] = heap[destination];
        heap[destination] = cache;
    }

    /**
     * 计算父节点下标
     */
    private int getParent(int child) {
        return (child + 1) / 2 - 1;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder("[");
        for (int i = 0;i<size;i++){
            sb.append(heap[i]);
            if(i!=size-1) sb.append(",");
        }
        return sb.append("]").toString();
    }

    public static void main(String[] args) {
        MaxHeap heap = new MaxHeap(new int[]{30,15,5,11,22,2});
        System.out.println(heap);
        while (heap.size()!=0){
            //堆排序得到一个序列
            int head = heap.removeAt(0);
            System.out.println(head);
        }
        //操作完后数组里元素的是从小到大排序的
        System.out.println(Arrays.toString(heap.heap));
    }
}

运行结果:

[30,22,5,11,15,2]
30
22
15
11
5
2
[2, 5, 11, 15, 22, 30]

堆排序算法Java实现

实际的堆排序中,我们肯定不用写这么长一段代码,专门把排序的逻辑提取出来就行了:

把数组看成一个最大堆(无序部分)和一个有序部分,每次将无序部分堆化一次(第一次构建堆的堆化是最耗时的,后面的堆化只需要向下堆化就好),然后第一个元素就是无序部分中最大的元素,与无序部分最后一个元素进行交换,然后并入有序部分

代码参考堆排序算法思路以及Java实现_long_lance的博客-CSDN博客,但是这里面的代码有错误,我进行了修改。

public class HeapSorting {
    public static void main(String[] args) {
        int[] a=new int[]{9,8,1,5,6,10,2};
        Sort(a);
        for(int i:a){
            System.out.println(i);
        }
    }

    //通过递归向下堆化
    public static void MaxHeapify(int[] a,int index,int size){
        int l=2*index;
        int r=2*index+1;
        int largest=index;
        if(l<=size && a[l]>a[index]){
            largest=l;
        }
        if(r<=size && a[r]>a[largest]){
            largest=r;
        }
        if(largest!=index){
            int temp=a[largest];
            a[largest]=a[index];
            a[index]=temp;
            MaxHeapify(a,largest,size);
        }
    }

    //数组堆化,注意上面实现堆的代码中构建堆是通过向上堆化,我们可以优化成将所有非叶节点向下堆化
    public static void HeapBuild(int[] a){
        for(int i=(a.length-1)/2;i>=0;i--){
            MaxHeapify(a,i,a.length-1);
        }
    }

    public static void Sort(int[] a){
        //构建堆
        HeapBuild(a);
        for(int i=a.length-1;i>=1;i--){
            //每次将堆顶元素交换到未排序部分末尾,然后再向下堆化
            int temp=a[i];
            a[i]=a[0];
            a[0]=temp;
            MaxHeapify(a,0,i-1);
        }
    }
}

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/%e5%b8%a6%e6%9c%89%e4%bc%98%e5%85%88%e7%ba%a7%e7%9a%84%e5%ae%8c%e5%85%a8%e4%ba%8c%e5%8f%89%e6%a0%91-%e5%a0%86/

发表评论

电子邮件地址不会被公开。