Java代码为例讲解堆的性质和基本操作以及排序方法

什么是堆？

堆（Heap）是一种基于二叉树的数据结构，常用于排序和优先级队列中。堆又分为大根堆和小根堆，大根堆满足任意节点的值都不大于其父节点的值，小根堆则相反。这里我们以大根堆为例。

堆的基本操作

插入元素

堆的插入操作是往堆中添加新值并保证堆的性质不变。具体实现如下：

public void insert(int value) {
    if (size == maxsize)
        return;
    heap[size] = value;
    int current = size;
    while (heap[current] > heap[parent(current)]) {
        swap(current, parent(current));
        current = parent(current);
    }
    size++;
}

其中，size为当前堆中元素数量，maxsize为堆的最大容量，heap为堆的数组，parent(current)为当前节点的父节点，swap(current, parent(current))为交换当前节点和父节点。

删除元素

堆的删除操作是删除堆的根节点并保持堆的性质。具体实现如下：

public int delete() {
    int popped = heap[0];
    heap[0] = heap[--size];
    heapify(0);
    return popped;
}

public void heapify(int index) {
    int largest = index;
    int left = leftChild(index);
    int right = rightChild(index);
    if (left < size && heap[left] > heap[largest])
        largest = left;
    if (right < size && heap[right] > heap[largest])
        largest = right;
    if (largest != index) {
        swap(index, largest);
        heapify(largest);
    }
}

其中，popped为删除的元素，leftChild(index)为当前节点的左侧子节点，rightChild(index)为当前节点的右侧子节点。

建立堆

如果给定的无序数组需要排序，可以先将其构建成一个堆再进行排序。建立堆的过程称为堆化。具体实现如下：

public void buildHeap(int[] arr) {
    if (arr.length > maxsize)
        return;
    size = arr.length;
    heap = Arrays.copyOf(arr, maxsize);
    for (int i = (size - 2) / 2; i >= 0; i--) {
        heapify(i);
    }
}

其中，arr为给定的数组，Arrays.copyOf(arr, maxsize)为将arr数组复制到大小为maxsize的heap数组中，(size - 2) / 2为最后一个非叶子节点的下标。

排序方法

堆排序

堆排序以大根堆为例，其基本思路是先将待排序序列构建成一个大根堆，再不断将堆的根节点和堆的最后一个非空节点交换，然后将堆的大小减1，再进行调整，直到堆的大小为1为止。

具体实现如下：

public void heapSort(int[] arr) {
    buildHeap(arr);
    for (int i = size-1; i > 0; i--) {
        swap(0, i);
        size--;
        heapify(0);
    }
}

其中，buildHeap(arr)为构建堆，swap(0, i)为交换第一个元素（堆的根节点）和第i个元素。

示例1：

假设给定一个无序序列[4, 10, 3, 5, 1, 8, 9]，进行堆排序后的结果应该是[1, 3, 4, 5, 8, 9, 10]。

int[] arr = {4, 10, 3, 5, 1, 8, 9};
HeapSort hs = new HeapSort();
hs.heapSort(arr);
System.out.println(Arrays.toString(arr));

输出结果为[1, 3, 4, 5, 8, 9, 10]。

示例2：

假设给定一个无序序列[6, 3, 7, 8, 1, 4, 5, 9, 2]，求第K大的数，这里以K=2为例。

int[] arr = {6, 3, 7, 8, 1, 4, 5, 9, 2};
HeapSort hs = new HeapSort();
hs.buildHeap(arr);
for (int i = 0; i < 2; i++) {
    hs.delete();
}
System.out.println(hs.delete());

输出结果为8，即第2大的数为8。

总结

堆是一种基于二叉树的数据结构，常用于排序和优先级队列中。堆的基本操作包括插入元素、删除元素和建立堆，其中建立堆是进行堆排序的先决条件。堆排序的基本思路是先将待排序序列构建成一个大根堆，再不断将堆的根节点和堆的最后一个非空节点交换，然后将堆的大小减1，再进行调整，直到堆的大小为1为止。