java算法之自定义堆结构：构造大顶堆_编程设计

/** 
 * @desc: 自定义堆结构：构造大顶堆，实现插入和删除操作 
 * @author: 毛会懂 
 * @create: 2021-01-06 10:35:00 
 **/ 
public class MyHeap<T extends Comparable<T>>{ 
    private T[] arr; 
    private Integer size; 
 
    public MyHeap(Integer size){ 
        arr = (T[])new Comparable[size + 1]; 
        this.size = 0; 
    } 
 
    //堆的大小 
   public Integer getSize(){ 
        return size; 
   } 
 
    //插入元素,插入到数组的最后一个元素 
    public void add(T t){ 
        arr[++size] = t; 
        //上浮 
        swim(size); 
    } 
 
    //删除元素 
    public T delMax(){ 
        T t =arr[1]; 
        //先交换第一个和最后一个元素。 
        exec(1,size); 
        size--; 
        //下沉 
        sink(1); 
        //删除最后一个元素（直接返回） 
        return t; 
    } 
 
    //上浮 
    private void swim(int k){ 
        if(k <= 1){ 
            return; 
        } 
        while (k>1) { 
            if (great(k, k / 2)) { 
                exec(k, k / 2); 
            } 
            k = k/2; 
        } 
    } 
 
    //下沉 
    private void sink(int k){ 
       while (2 * k <= size){ 
           //先找子节点最大值 
           int max; 
           if(2 * k + 1 < size) { 
               if (great(2 * k, 2 * k + 1)) { 
                   max = 2 * k; 
               } else { 
                   max = 2 * k + 1; 
               } 
           }else{ 
               max = 2 * k; 
           } 
 
           if(great(max,k)){ 
               exec(max,k); 
           } 
           k = max; 
       } 
    } 
 
    //交换两个元素位置 
    private void exec(int i,int j){ 
        T t = arr[i]; 
        arr[i] = arr[j]; 
        arr[j] = t; 
    } 
 
    //比较两个元素的大小(arr[i]大，返回True) 
    private Boolean great(int i,int j){ 
        return arr[i].compareTo(arr[j]) > 0; 
    } 
}

测试代码：

//构造堆结构
public static void main(String[] args) {
    char[] chars = {'A','H','D','O','E','W','G','T'};
    MyHeap<Character> myHeap = new MyHeap<>(20);
    for(int i = 0;i < chars.length;i++){
        myHeap.add(chars[i]);
    }

    System.out.println("---------");

    for(int i = 0;i < chars.length;i++){
        System.out.print(myHeap.delMax() + ", ");
    }
    System.out.println("over");
}

本文参考链接：https://www.cnblogs.com/maohuidong/p/14245643.html