基本数据结构

最小（大）堆

最小堆的主要操作：

• 将已有数组进行堆化
• 向最小堆中的添加，删除操作
• 将最小堆的数组排序化

堆化已有数组

从最后一个非叶子节点开始向下调整。

向下调整：

• 选择左右儿子中值更大且大于本节点值的节点，与本节点交换位置（本节点值大于左右儿子时不需要操作）
• 交换后，将交换后的儿子节点继续执行向下调整

向上调整：

• 将儿子元素与父亲比较，如果儿子元素大于父亲元素，则与父亲元素交换
• 交换后，堆交换后的父亲节点继续执行向上调整

在一个完全二叉树中，最后一个非叶子节点是 $n/2-1$，对所有的非叶子节点执行向下调整。完成后数组elements即成为最小（大）堆。

添加元素：将元素添加到数组最后（完全二叉树最后一个叶子节点）然后对该元素执行向上调整

删除元素：删除根节点元素（数组第一个元素），将最后一个元素赋值给根节点并对根节点执行向下调整

import java.util.Arrays;

public class minHeap<T extends Comparable<T>> {
    private T[] elements;

    public minHeap(T[] arr) {
        elements = Arrays.copyOf(arr, arr.length);        
        // 对所有非叶子节点执行向下调整
        for (int i = arr.length / 2 - 1; i >= 0; i--) {
            downMove(elements, i, elements.length - 1);
        }
    }
	//向下调整
    public void downMove(T[] elements, int start, int end) {
        int parent = start;
        for (int i = start * 2 + 1; i <= end; i = i * 2 + 1) {
            //选择左右儿子中较大的
            if (i < end && elements[i].compareTo(elements[i + 1]) < 0) {
                i++;
            }
            //如果较大的儿子比父亲值还大，需要交换位置，并对儿子节点继续向下调整，否则退出循环
            if (elements[i].compareTo(elements[parent]) > 0) {
                T tmp = elements[parent];
                elements[parent] = elements[i];
                elements[i] = tmp;
                parent = i;
            } else {
                break;
            }
        }
    }

}

package ds;

import java.util.Arrays;

public class minHeap<T extends Comparable<T>> {
    private T[] elements;
    private int size;

    public minHeap(T[] arr, int size) {
        size = arr.length;
        elements = Arrays.copyOf(arr, Math.max(arr.length, size));
        // 对所有非叶子节点执行向下调整
        for (int i = arr.length / 2 - 1; i >= 0; i--) {
            downMove(elements, i, elements.length - 1);
        }
    }

    // 向下调整
    private void downMove(T[] elements, int start, int end) {
        int parent = start;
        for (int i = start * 2 + 1; i <= end; i = i * 2 + 1) {
            // 选择左右儿子中较大的
            if (i < end && elements[i].compareTo(elements[i + 1]) < 0) {
                i++;
            }
            // 如果较大的儿子比父亲值还大，需要交换位置，并对儿子节点继续向下调整，否则退出循环
            if (elements[i].compareTo(elements[parent]) > 0) {
                T tmp = elements[parent];
                elements[parent] = elements[i];
                elements[i] = tmp;
                parent = i;
            } else {
                break;
            }
        }
    }

    private void upMove(T[] elements, int start) {
        int child = start;
        for (int i = (start - 1) / 2; i > 0; i = (i - 1) / 2) {
            if (elements[child].compareTo(elements[i]) > 0) {
                T tmp = elements[child];
                elements[child] = elements[i];
                elements[i] = tmp;
                child = i;
            }
        }
    }

    // 添加元素至最后一个位置并向上调整
    public void add(T element) {
        elements[size] = element;
        upMove(elements, size);
        size++;
    }

    // 最后一个元素覆盖第一个元素并向下调整
    public void remove() {
        elements[0] = elements[size - 1];
        size--;
        downMove(elements, 0, size);
    }

    public T[] heapSort() {
        sortArrayFromHeap(elements);
        return elements;
    }

    private void sortArrayFromHeap(T[] elements) {
        for (int i = elements.length - 1; i > 0; i--) {
            T tmp = elements[0];
            elements[0] = elements[i];
            elements[i] = tmp;
            downMove(elements, 0, i - 1);
        }
    }

    public static void main(String[] args) {
        int[] arr = { -4, 0, 7, 4, 9, -5, -1, 0, -7, -1 };
        Integer[] arrInteger = Arrays.stream(arr).boxed().toArray(Integer[]::new);
        minHeap<Integer> m = new minHeap<>(arrInteger, arrInteger.length + 10);
        m.add(10);
        int[] res = Arrays.stream(m.elements).mapToInt(Integer::intValue).toArray();
        System.out.println(Arrays.toString(res));
    }
}