A simple heap implemented in Java.

SimpleHeap.java

import java.util.Arrays;

/**
 * 大顶堆实现
 */
public class SimpleHeap {

    public static void main(String[] args) {
        SimpleHeap heap = new SimpleHeap(10);
        heap.put(1);
        heap.put(2);
        heap.put(3);
        heap.put(4);
        heap.put(5);
        heap.put(6);
        heap.put(7);
        heap.put(8);
        heap.put(9);
        heap.put(10);
        // Debug: System.out.println(heap.toString());
        heap.delete(10);
        heap.put(11);
        // Debug: System.out.println(heap.toString());

        // Debug: int[] arr = Utils.createRandomArray();
        // Debug: HeapSort.sortOpt(arr);
        // Debug: System.out.println(Arrays.toString(arr));
    }


    private int[] data;
    private int size;

    public SimpleHeap(int maxSize) {
        data = new int[maxSize];
    }


    /**
     * 向堆中插入元素
     * 1. 插入到堆底
     * 2. 逐渐向上比较，如果比父节点大，则交换
     *
     * @param key 要插入的key
     */
    public void put(int key) {
        if (size == data.length) {
            throw new RuntimeException("heap is full");
        }
        data[size] = key;
        if (size > 0) {
            shiftUp();
        }
        size++;
    }

    private int indexOf(int key) {
        for (int i = 0; i < size; i++) {
            if (key == data[i]) {
                return i;
            }
        }
        return -1;
    }

    /**
     * 堆删除操作
     * 1. 将最后一个元素放入要删除的位置
     * 2. 从当前位置逐渐向下调整
     *
     * @param key 要删除的键
     */
    public void delete(int key) {
        if (size == 0) {
            return;
        }
        int keyIndex = indexOf(key);
        int lastIndex = size - 1;
        swap(keyIndex, lastIndex);
        data[lastIndex] = 0;
        size--;
        shiftDown(keyIndex);
    }

    private void shiftDown(int index) {
        int keyIndex = index;
        while (keyIndex < size) {
            int left = keyIndex * 2 + 1;
            int right = keyIndex * 2 + 2;
            int maxPos = left < size && data[left] > data[keyIndex] ? left : keyIndex;
            maxPos = right < size && data[right] > data[maxPos] ? right : maxPos;
            if (maxPos == keyIndex) {
                break;
            } else {
                swap(maxPos, keyIndex);
            }
            keyIndex = maxPos;
        }
    }

    private void shiftUp() {
        int parentIndex = (size - 1) >> 1;
        int keyIndex = size;
        while (parentIndex >= 0) {
            if (data[parentIndex] < data[keyIndex]) {
                swap(parentIndex, keyIndex);
            } else {
                break;
            }
            keyIndex = parentIndex;
            parentIndex = (parentIndex - 1) >> 1;
        }
    }

    private void swap(int from, int to) {
        int temp = data[from];
        data[from] = data[to];
        data[to] = temp;
    }

    private int getTop() {
        return data[0];
    }

    /**
     * 返回并删除堆顶的元素
     *
     * @return 堆顶
     */
    public int peekTop() {
        int top = getTop();
        delete(top);
        return top;
    }


    @Override
    public String toString() {
        return Arrays.toString(data);
    }

    /**
     * 堆排序
     */
    static class HeapSort {

        /**
         * 使用最大堆进行排序
         *
         * @param arr 要排序的数据
         */
        public static void sort(int[] arr) {
            SimpleHeap heap = new SimpleHeap(arr.length);
            for (int i = 0; i < arr.length; i++) {
                int num = arr[i];
                heap.put(num);
            }
            int index = heap.size - 1;
            while (heap.size > 0) {
                arr[index--] = heap.peekTop();
            }
        }


        /**
         * 原地堆排序，优化版本
         * 1. 从原地建堆，从n/2 到 0 需要向下调整
         */
        public static void sortOpt(int[] arr) {
            // 从上向下堆化
            for (int i = (arr.length - 2) / 2; i > 0; i--) {
                heapify(arr, arr.length, i);
            }
            // 将堆顶移动到数组中，即将堆顶和最后的元素交换位置，然后重新heapify
            // 当前堆为n，逐渐减少
            int n = arr.length;
            while (n > 0) {
                int temp = arr[n - 1];
                arr[n - 1] = arr[0];
                arr[0] = temp;
                heapify(arr, n - 1, 0);
                n--;
            }
        }

        /**
         * 从上向下堆化
         */
        private static void heapify(int[] arr, int length, int index) {
            int kindex = index;
            while (kindex < length) {
                int left = kindex * 2 + 1;
                int right = kindex * 2 + 2;

                int maxIndex = left < length && arr[left] > arr[kindex] ? left : kindex;
                maxIndex = right < length && arr[right] > arr[maxIndex] ? right : maxIndex;
                if (maxIndex != kindex) {
                    int temp = arr[kindex];
                    arr[kindex] = arr[maxIndex];
                    arr[maxIndex] = temp;
                    kindex = maxIndex;
                } else {
                    break;
                }
            }
        }
    }
}