详解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实现小顶堆和大顶堆内容请搜索www.887551.com以前的文章或继续浏览下面的相关文章希望大家以后多多支持www.887551.com！