堆&堆排序

public class Heap {

    private int size;

    private int[] data;

    public Heap(int maxSize) {
        this.data = new int[maxSize];
    }

    private void swap(int a, int b) {
        int tmp = data[a];
        data[a] = data[b];
        data[b] = tmp;
    }

    private int left(int index) {
        return index << 1 ^ 1;
    }

    private int right(int index) {
        return (index + 1) << 1;
    }

    private int parent(int index) {
        return (index - 1) >> 1;
    }

    public void up(int index) {
        int tmp = data[index];

        while (index != 0) {
            int parent = parent(index);

            if (data[parent] < tmp) {
                data[index] = data[parent];
                index = parent;
            } else {
                break;
            }

        }
        data[index] = tmp;
    }

    public void add(int x) {
        data[size] = x;
        up(size ++);
    }

    public void down(int index) {
        int left, right;

        while ((left = left(index)) < size) {

            int maxIndex = index;

            if (data[left] > data[maxIndex]) {
                maxIndex = left;
            }

            if ((right = right(index)) < size && data[right] > data[maxIndex]) {
                maxIndex = right;
            }

            if (maxIndex != index) {
                swap(index, maxIndex);
                index = maxIndex;
            } else {
                break;
            }

        }
    }

    public int getMax() {
        if (size == 0) {
            throw new IndexOutOfBoundsException();
        }
        return data[0];
    }

    public int popMax() {
        if (size == 0) {
            throw new IndexOutOfBoundsException();
        }
        int max = data[0];
        data[0] = data[-- size];
        down(0);
        return max;
    }

    public void update(int index, int x) {
        if (index >= size) {
            throw new IndexOutOfBoundsException();
        }
        data[index] = x;
        up(index);
        down(index);
    }

    public int remove(int index) {
        if (index >= size) {
            throw new IndexOutOfBoundsException();
        }
        int res = data[index];
        data[index] = data[-- size];
        up(index);
        down(index);
        return res;
    }
}

堆排序：

import java.util.Arrays;

public class HeapSort {

    public static void sort(int[] arr) {

        if (arr == null || arr.length == 0) {
            return;
        }

        Heap heap = new Heap(arr.length);

        for (int i = 0; i < arr.length; ++ i) {
            heap.add(arr[i]);
        }

        for (int i = arr.length - 1; i >= 0; -- i) {
            arr[i] = heap.popMax();
        }
    }

    public static void main(String[] args) {
        int[] arr = {2, 3, 4, 5, 7, 0, 1, 2, 10, 9};
        sort(arr);
        Arrays.stream(arr).forEach(System.out::println);
    }

}

堆&堆排序

原文：https://blog.51cto.com/tianyiya/2537804