如何用Java实现小顶堆和大顶堆

发布时间:2021-06-21 09:20:31 作者:chen
来源:亿速云 阅读:546

本篇内容主要讲解“如何用Java实现小顶堆和大顶堆”,感兴趣的朋友不妨来看看。本文介绍的方法操作简单快捷,实用性强。下面就让小编来带大家学习“如何用Java实现小顶堆和大顶堆”吧!

大顶堆

每个结点的值都大于或等于其左右孩子结点的值

小顶堆

每个结点的值都小于或等于其左右孩子结点的值

对比图

如何用Java实现小顶堆和大顶堆

实现代码

public class HeapNode{
    private int size;//堆大小
    private int[] heap;//保存堆数组

    //初始化堆
    public HeapNode(int n) {
        heap = new int[n];
        size = 0;
    }

    //小顶堆建堆
    public void minInsert(int key){
        int i = this.size;
        if (i==0) heap[0] = key;
        else {
            while (i>0 && heap[i/2]>key){
                heap[i] = heap[i/2];
                i = i/2;
            }
            heap[i] = key;
        }
        this.size++;
    }

    //大顶堆建堆
    public void maxInsert(int key){
        int i = this.size;
        if (i==0) heap[0] = key;
        else {
            while (i>0 && heap[i/2]<key){
                heap[i] = heap[i/2];
                i = i/2;
            }
            heap[i] = key;
        }
        this.size++;
    }

    //小顶堆删除
    public int minDelete(){
        if (this.size==0) return -1;
        int top = heap[0];
        int last = heap[this.size-1];
        heap[0] = last;
        this.size--;
        //堆化
        minHeapify(0);
        return top;
    }

    //大顶堆删除
    public int maxDelete(){
        if (this.size==0) return -1;
        int top = heap[0];
        int last = heap[this.size-1];
        heap[0] = last;
        this.size--;
        //堆化
        maxHeapify(0);
        return top;
    }

    //小顶堆化
    public void minHeapify(int i){
        int L = 2*i,R=2*i+1,min;
        if (L<=size && heap[L] < heap[i]) min = L;
        else min = i;
        if (R <= size && heap[R] < heap[min]) min = R;
        if (min!=i){
            int t = heap[min];
            heap[min] = heap[i];
            heap[i] = t;
            minHeapify(min);
        }
    }

    //大顶堆化
    public void maxHeapify(int i){
        int L = 2*i,R=2*i+1,max;
        if (L<=size && heap[L] > heap[i]) max = L;
        else max = i;
        if (R <= size && heap[R] > heap[max]) max = R;
        if (max!=i){
            int t = heap[max];
            heap[max] = heap[i];
            heap[i] = t;
            maxHeapify(max);
        }
    }

    //输出堆
    public void print(){
        for (int i = 0; i < this.size; i++) {
            System.out.print(heap[i]+" ");
        }
        System.out.println();
    }
}

测试

public class Heap {
    static int[] a = {5,3,6,4,2,1};
    static int n = a.length;
    public static void main(String[] args){
        HeapNode heapNode = new HeapNode(n);
        for (int i = 0; i < n; i++) {
            heapNode.maxInsert(a[i]);
        }
        heapNode.print();
        for (int i = 0; i < n; i++) {
            int min = heapNode.maxDelete();
            System.out.print("堆顶:"+min+" 剩下堆元素:");
            heapNode.print();
        }
    }
}

结果

如何用Java实现小顶堆和大顶堆

到此,相信大家对“如何用Java实现小顶堆和大顶堆”有了更深的了解,不妨来实际操作一番吧!这里是亿速云网站,更多相关内容可以进入相关频道进行查询,关注我们,继续学习!

推荐阅读:
  1. 堆的性质是什么?怎么实现堆?
  2. C++实现堆

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

java

上一篇:SpringBoot整合JPA的过程是怎样的

下一篇:Springboot-yaml配置和自动配置的原理是什么

相关阅读

您好,登录后才能下订单哦!

密码登录
登录注册
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》