【算法】堆排序---MapleYe

堆排序堆

堆是一种树形结构，在排序的过程中，把元素看成是一颗完全二叉树。用数组来表示一颗完全二叉树的话，对于每个节点 i 存在以下关系： 1）父节点 = (i - 1) / 2 2）左孩子 = 2 * i + 1 3）右孩子 = 2 * i + 2

大根堆，小根堆

父节点都比子节点大的堆成为大根堆，用于升序 父节点都比子节点小的堆成为小根堆，用于降序

如图所示：

算法思路

因此，我们需要把一个树构造成大根堆或小根堆，以大根堆为例子： 1）构造大根堆 2）把根节点和尾节点进行交换，堆的size-- 3）把剩余的堆进行调整，重新调整为大根堆 3）重复2，3步骤，直至堆的size为0

1、构造算法

每次插入一颗子节点，都与父节点进行比较，若比父节点大，则与父节点交换后，再重复以上步骤，直至不比父节点大。

/// 把下标为index的值插入，建立堆 /// 堆与数组的转换： /// 对于当前下标为index的数，其父亲为 (index - 1) / 2 /// 左节点为 2 * index + 1, 右节点为 2 * index + 2 public static void heapInsert(int[] arr, int index) { // 比父节点大，则交换，直至比父节点小 while (arr[index] > arr[(index - 1) / 2]) { swap(arr, index, (index - 1) / 2); index = (index - 1) / 2; } }2、调整算法

父节点依次与左右孩子比较，若其父节点小于左右孩子，则与左右孩子较大者交换，然后重复以上步骤，直至父节点大于左右孩子

/// 重新调整为大根堆，size表示：在数组建立了堆，堆的size public static void heapify(int arr[], int index, int size) { // 左节点 int left = index * 2 + 1; while(left < size) { // 右节点 int right = left + 1; // 设左孩子为最大 int largest = left; if (right < size) { // 存在右节点，选出其中最大的 largest = arr[left] > arr[right] ? left : right; } // 比较父节点和最大子节点的值 largest = arr[index] > arr[largest] ? index : largest; // 若当前节点就是最大的，则调整完毕 if (largest == index) { return; } // 否则交换 swap(arr, largest, index); // 继续以上过程 index = largest; left = index * 2 - 1; } }3、完整代码 public static void heapSort(int arr[]) { if (arr == null || arr.length < 2) { return; } // 建立大根堆 for(int i = 0; i < arr.length; i++) { heapInsert(arr, i); } int size = arr.length; // 将头部换到最后，开始调整，直至size = 0 swap(arr, 0, --size); while(size > 0) { heapify(arr, 0, size); swap(arr, 0, --size); } } /// 把下标为index的值插入，建立堆 /// 堆与数组的转换： /// 对于当前下标为index的数，其父亲为 (index - 1) / 2 /// 左节点为 2 * index + 1, 右节点为 2 * index + 2 public static void heapInsert(int[] arr, int index) { // 比父节点大，则交换，直至比父节点小 while (arr[index] > arr[(index - 1) / 2]) { swap(arr, index, (index - 1) / 2); index = (index - 1) / 2; } } /// 重新调整为大根堆，size表示：在数组建立了堆，堆的size public static void heapify(int arr[], int index, int size) { // 左节点 int left = index * 2 + 1; while(left < size) { // 右节点 int right = left + 1; // 设左孩子为最大 int largest = left; if (right < size) { // 存在右节点，选出其中最大的 largest = arr[left] > arr[right] ? left : right; } // 比较父节点和最大子节点的值 largest = arr[index] > arr[largest] ? index : largest; // 若当前节点就是最大的，则调整完毕 if (largest == index) { return; } // 否则交换 swap(arr, largest, index); // 继续以上过程 index = largest; left = index * 2 - 1; } } public static void swap(int[] arr, int i, int j) { int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; } ---来自腾讯云社区的---MapleYe