一般堆

package com.company.stucts.binarytree.heap;
/*来自 nowjava.com - 时  代  Java*/

import java.util.ArrayList;

import java.util.Comparator;

import java.util.List;


@SuppressWarnings({ "Duplicates", "WeakerAccess" })

public class Heap<T> {

    private static final int DEFAULT_HEAP_CAPACITY = 100;


    private final List<T> arrayList;

    private final Comparator<T> comparator;


    public Heap(Comparator<T> comparator) {

        this(comparator, DEFAULT_HEAP_CAPACITY);

    }


    public Heap(Comparator<T> comparator, int size) {/**NowJava.com - 时  代  Java**/

        this.comparator = comparator;

        arrayList = new ArrayList<>(size);

    }


    public void add(T element) {

        arrayList.add(element);

        moveUp(arrayList.size() - 1);

    }


    public T extractTop() {

        if (arrayList.size() == 0)

            return null;

        if (arrayList.size() == 1)

            return arrayList.remove(0);


        T topElement = arrayList.get(0);

        T lastElement = arrayList.remove(arrayList.size() - 1);

        arrayList.set(0, lastElement);

        moveDown(0);

        return topElement;

    }


    private void moveUp(int childIndex) {

        if (childIndex > 0) {

            int parentIndex = (childIndex - 1) / 2;


            T parent = arrayList.get(parentIndex);

            T child = arrayList.get(childIndex);


            if (comparator.compare(parent, child) < 0) {

                arrayList.set(parentIndex, child);

                arrayList.set(childIndex, parent);

                moveUp(parentIndex);

            }

        }

    }


    private void moveDown(int parentIndex) {

        int childIndex = parentIndex * 2 + 1;

        if (childIndex < arrayList.size()) {

            if (childIndex + 1 < arrayList.size()) {

                // select best of two child elements

                T child1 = arrayList.get(childIndex);

                T child2 = arrayList.get(childIndex + 1);

                if (comparator.compare(child1, child2) < 0) {

                    childIndex++;

                }

            }


            T parent = arrayList.get(parentIndex);

            T child = arrayList.get(childIndex);


            if (comparator.compare(parent, child) < 0) {

                arrayList.set(parentIndex, child);

                arrayList.set(childIndex, parent);

                moveDown(childIndex);

            }

        }

    }


    @Override

    public String toString() {

        return "Heap{" + "arrayList=" + arrayList + ", size: "

                + arrayList.size() + '}';

    }


    /**

     * Test main method

     */

    public static void main(String[] args) {