java 小根堆 排序_堆排序 - Java

堆排序是一种常见的排序算法，具有稳定性高、效率高等优点。下面介绍一下使用Java实现的小根堆排序。

首先，我们需要定义一个小根堆类，用于存储待排序的数据。该类需要包含以下几个方法：

1. `Heap()`：构造函数，用于初始化小根堆。

2. `insert(int val)`：插入操作，将一个新的元素插入到小根堆中。

3. `deleteMin()`：删除操作，删除小根堆中的最小元素，并返回该元素的值。

4. `size()`：获取小根堆中元素的个数。

5. `isEmpty()`：判断小根堆是否为空。

接下来，我们就可以使用小根堆对待排序的数据进行排序了。具体的步骤如下：

1. 将待排序的数据存入小根堆中。

2. 依次从小根堆中删除最小元素，并将其存入数组中。

3. 最后，将数组反转，即可得到排序后的结果。

下面是具体的Java代码实现：

public class HeapSort {
    public static void heapSort(int[] arr) {
        Heap heap = new Heap(arr.length);
        for (int i = 0; i < arr.length; i++) {
            heap.insert(arr[i]);
        }
        for (int i = 0; i < arr.length; i++) {
            arr[i] = heap.deleteMin();
        }
        // 反转数组
        reverse(arr);
    }
    // 反转数组
    private static void reverse(int[] arr) {
        int left = 0;
        int right = arr.length - 1;
        while (left < right) {
            int temp = arr[left];
            arr[left] = arr[right];
            arr[right] = temp;
            left++;
            right--;
        }
    }
    // 小根堆类
    static class Heap {
        private int[] heap;
        private int size;
        public Heap(int capacity) {
            heap = new int[capacity + 1];
            size = 0;
        }
        public void insert(int val) {
            if (size == heap.length - 1) {
                throw new RuntimeException("Heap is full");
            }
            int i = ++size;
            while (i != 1 && val < heap[i / 2]) {
                heap[i] = heap[i / 2];
                i /= 2;
            }
            heap[i] = val;
        }
        public int deleteMin() {
            if (isEmpty()) {
                throw new RuntimeException("Heap is empty");
            }
            int min = heap[1];
            int last = heap[size--];
            int i = 1;
            int child = 2;
            while (child <= size) {
                if (child < size && heap[child] > heap[child + 1]) {
                    child++;
                }
                if (last > heap[child]) {
                    heap[i] = heap[child];
                    i = child;
                    child *= 2;
                } else {
                    break;
                }
            }
            heap[i] = last;
            return min;
        }
        public int size() {
            return size;
        }
        public boolean isEmpty() {
            return size == 0;
        }
    }
}

使用该算法对数组进行排序：

int[] arr = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
HeapSort.heapSort(arr);
System.out.println(Arrays.toString(arr)); // 输出 [1, 1, 2, 3, 3, 4, 5, 5, 5, 6, 9]