实现

import java.util.ArrayList;

/**
 * 大根堆
 */
public class MaxHeap {

    private final ArrayList<Integer> list = new ArrayList<Integer>();

    /**
     * 添加元素
     *
     * @param value
     */
    public void push(int value) {
        list.add(value);
        int lastIndex = list.size() - 1;
        adjustUp((lastIndex - 1) / 2);
    }

    /**
     * 移除最大的元素
     *
     * @return
     */
    public Integer pull() {
        if (list.isEmpty()) return null;
        Integer value = list.get(0);
        int lastIndex = list.size() - 1;
        list.set(0, list.get(lastIndex));
        list.remove(lastIndex);
        adjustDown(0);
        return value;
    }

    /**
     * 向下调整算法，将index节点的数据不断向树的叶子节点移动
     *
     * @param index
     */
    private void adjustDown(int index) {
        int lastIndex = list.size() - 1;
        if (index > (lastIndex - 1) / 2 || lastIndex == 0) return;
        int left = index * 2 + 1, right = index * 2 + 2;
        int largest = left;
        if (right <= lastIndex && list.get(right) > list.get(left)) {
            largest = right;
        }
        if (list.get(index) < list.get(largest)) {
            swap(index, largest);
            adjustDown(largest);
        }
    }


    /**
     * 向上调整算法，将index节点的子节点的数据不断向树的父节点移动
     *
     * @param index
     */
    private void adjustUp(int index) {
        if (index < 0) return;
        int left = index * 2 + 1, right = index * 2 + 2;
        int lastIndex = list.size() - 1;
        if (left > lastIndex) return;
        int largest = left;
        if (right <= lastIndex && list.get(right) > list.get(left)) {
            largest = right;
        }
        if (list.get(index) < list.get(largest)) {
            swap(index, largest);
            adjustUp((index - 1) / 2);
        }
    }

    private void swap(int i, int j) {
        Integer temp = list.get(i);
        list.set(i, list.get(j));
        list.set(j, temp);
    }
}

测试

import java.util.Random;

/**
 * 测试类
 */
class TestMaxHeap {

    public static void main(String[] args) {
        MaxHeap maxHeap = new MaxHeap();
        Random random = new Random();
        int size = 10 + Math.abs(random.nextInt()) % 7;
        System.out.println("size:" + size);
        for (int i = 0; i < size; i++) {
            maxHeap.push(Math.abs(random.nextInt()) % 1000);
        }
        Integer v;
        while ((v = maxHeap.pull()) != null) {
            System.out.print(v);
            System.out.print(" ");
        }
    }
}