算法与数据结构系列之[最大堆-下]

上篇贴出了最大堆的C语言代码实现，这篇贴出最大堆的java代码实现：

public class MaxHeap<E extends Comparable<E>> {

    private Array<E> data;

    public MaxHeap(int capacity){
        data = new Array<>(capacity);
    }

    public MaxHeap(){
        data = new Array<>();
    }
    //堆的heapify操作，将一个任意的数组转换为堆结构
    //如果不使用heapify操作构建堆，创建n个元素的堆，时间复杂度为O(nlogn),使用heapify操作，时间复杂度为O(n)
    public MaxHeap(E[] arr){
        data = new Array<>(arr);
        for(int i = parent(arr.length - 1);i>= 0; i--){
            siftDown(i);
        }
    }
    //判断堆是否为空
    public boolean isEmpty(){
        return data.isEmpty();
    }

    //返回堆中元素个数
    public int getSize(){
        return data.getSize();
    }

    //返回给定索引表示的父节点在数组中的索引
    private int parent(int index){
        if(index == 0)
            throw new IllegalArgumentException("根节点没有父节点");
        return (index - 1)/2;
    }

    //返回给定索引表示的左孩子节点的索引
    private int leftChild(int index){
        return index * 2 + 1;
    }

    //返回给定索引表示的右孩子的索引
    private int rightChild(int index){
        return index * 2 + 2;
    }


    //向堆中添加元素
    public void add(E e){
        data.addLast(e);
        siftUp(data.getSize() - 1);
    }

    private void siftUp(int k){
        while (k > 0 && data.get(parent(k)).compareTo(data.get(k)) < 0){
            data.swap(k,parent(k));
            k = parent(k);
        }
    }

    //查找堆中最大元素
    public E findMax(){
        if(data.getSize() == 0)
            throw  new IllegalArgumentException("堆为空");
        return data.get(0);
    }

    //删除堆中最大元素
    public E extractMax(){
        E ret = findMax();
        data.swap(0,data.getSize() - 1);
        data.removeLast();
        siftDown(0);
        return ret;
    }

    private void siftDown(int k) {
        while (leftChild(k) < data.getSize()){
            int j = leftChild(k);
            if(j + 1 < data.getSize() && data.get(j + 1).compareTo(data.get(j)) > 0)
                j = rightChild(k);    //data[j]是左右子节点中最大的那个
            if(data.get(k).compareTo(data.get(j)) >= 0)
                break;
            data.swap(k,j);
            k = j;
        }
    }

    //将堆中最大元素替换成e
    public E replace(E e){
        E res = findMax();
        data.set(0,e);
        siftDown(0);
        return res;
    }

    public static void main(String[] args) {
        int[] num = {62,42,30,28,15,22,13,19,17,14};
        MaxHeap<Integer> heap = new MaxHeap<>();
        for (int i = 0; i < num.length; i++) {
            heap.add(num[i]);
        }
        int[] arr = new int[heap.getSize()];
        for (int i = 0; i < num.length; i++) {
            arr[i] = heap.extractMax();
        }
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }
}