自定义最大堆

package com.njau.dataStructure;

import java.util.ArrayList;
import java.util.PriorityQueue;

/** * @author 张文军 * @Description:自定义最大堆 * @Company:南京农业大学工学院 * @version:1.0 * @date 2019/9/713:00 */
public class MaxHeap<E extends Comparable<E>> {
    private ArrayList<E> data;

    public MaxHeap() {
        this.data = new ArrayList<E>();
    }

    public int getSize() {
        return data.size();
    }

    public Boolean isEmpty() {
        return data.size() == 0;
    }

    /** * 返回父亲节点的索引 * * @param index 当前节点 * @return 父亲节点 */
    private int parent(int index) {
        if (index == 0) {
            throw new RuntimeException("index-0 doesn`t have parent ");
        }
        return (index - 1) / 2;
    }

    /** * 返回左孩子节点的索引 * * @param index 当前节点 * @return 当前索引的左孩子的索引 */
    private int leftChild(int index) {
        return index * 2 + 1;
    }

    /** * 返回右孩子节点的索引 * * @param index 当前节点 * @return 当前索引的右孩子的索引 */
    private int rightChild(int index) {
        return index * 2 + 2;
    }

    public void add(E e) {
        data.add(e);
        siftUp(data.size() - 1);
    }

    /** * 用浮动的方式调整堆中新添加的元素的位置 * @param index */
    private void siftUp(int index) {
        /** * 节点索引小于1 并且 节点值大于父亲节点时进行调整 */
        while (index > 0 && data.get(parent(index)).compareTo(data.get(index)) < 0) {
            /** * 节点交换 */
            swap(parent(index), index);
        }
    }

    /** * 交换元素 * @param parent 当前节点的父节点 * @param index 当前节点 */
    private void swap(int parent, int index) {
        if (parent < 0 || parent > data.size() || index < 0 || index > data.size()) {
            throw new RuntimeException("Index is illegal ");
        }
        E e = data.get(parent);
        data.set(parent, data.get(index));
        data.set(index, e);
    }

    /** * 取出堆中最大元素 并重新调整堆结构 * @return */
    public E ExtractMax() {
        E ret = fundMax();
        /** * 将首个元素和微元素交换位置 */
        swap(0, data.size() - 1);
        /** * 删除尾元素 */
        data.remove(data.size() - 1);
        /** * 调整节点位置 */
        siftDown(0);
        return ret;
    }

    /** * 用下沉的方式 调整当前节点和左右子节点的位置 * @param index 当前节点索引 */
    private void siftDown(int index) {
        PriorityQueue<E> priorityQueue = new PriorityQueue<>();
    }

    /** * 查看堆中最大元素 * @return 堆中最大元素 */
    private E fundMax() {
        if (data.size() == 0) {
            throw new RuntimeException("Can not findMax when heap is empty ");
        }
        return data.get(0);
    }

}