堆排序学习笔记

本文是笔者阅读《Introduction to Algorithms》所做的笔记。

堆

堆数据结构是一个数组对象，我们可以把它看成一个完全二叉树

表示堆的数组有两个属性，数组的长度和堆的大小（堆内元素的数量）

假设有数组arr=[16, 14, 10, 8, 7, 9, 3, 2, 4, 1]

其表示的堆为：

如果数组arr里的元素是基于1进行索引化的，如果已知堆中某节点的索引i，结合上图，可以推导出它的父节点、左子节点、右子节点的索引。代码如下：

public int parent(int i) {
  return i / 2;
}

public int left(int i) {
  return i * 2;
}

public int right(int i) {
  return i * 2 + 1;
}

如果数组的索引是基于0开始的，则有：

public static int parent(int i) {
  return (i + 1) / 2 - 1;
}

public static int left(int i) {
  return 2 * (i + 1) - 1;
}

public static int right(int i) {
  return 2 * (i + 1);
}

二插堆分类

二插堆有两类，最大堆和最小堆。

最大堆有最大堆属性，即任一除根节点外的其它节点的值都小于等于其父节点的值。

最小堆有最小堆属性，即任一节点的值都大于等于其父节点的值。

维持最大堆属性

下面将实现一个方法maxHeapify，用来维护最大堆属性。它以数组arr和索引i作为参数。当调用时，假设节点i的左子树和右子树是最大堆。但是根节点为i的树可能违反最大堆属性。

maxHeapify让节点i向下移动，以维持最大堆属性。

public static void maxHeapify(int[] arr, int i, int heapSize) {
  int left = left(i);
  int right = right(i);
  int largest = i;
  if (left < heapSize && arr[left] > arr[largest]) {
    largest = left;
  }
  if (right < heapSize && arr[right] > arr[largest]) {
    largest = right;
  }

  if (largest != i) {
    int temp = arr[i];
    arr[i] = arr[largest];
    arr[largest] = temp;
    maxHeapify(arr, largest, heapSize);
  }
}

构建最大堆

可以通过以从底向上的方式，调用maxHeapify方法，把数组arr转换成一个最大堆。

代码如下：

public void buildMaxHeap(int[] arr) {
  for(int i = arr.length / 2 - 1; i >= 0; i--) {
    maxHeapify(arr, i);
  }
}

堆排序升序排序

堆排序可以通过使用buildMaxHeap方法开始，把数组arr构建一个最大堆。由于最大的元素是arr[ 0 ]，可以把它放在排序后正确的位置，即arr[arr.length - 1]。

接着，在把数组中0 ～ arr.length - 2范围内的元素构建成一个最大堆，再交换arr[ 0 ] 与 arr[ arr.length - 2] 的位置。

以此类推。

最终，得到排序的后数组。

代码如下：

public static void heapSort(int[] arr) {
  buildMaxHeap(arr);
  for (int i = arr.length - 1; i > 0; i--) {
    int temp = arr[0];
    arr[0] = arr[i];
    arr[i] = temp;
    maxHeapify(arr, 0, i);
  }
}

堆排序全部代码

public class HeapSortUtils {
  public static int parent(int i) {
    return (i + 1) / 2 - 1;
  }

  public static int left(int i) {
    return 2 * (i + 1) - 1;
  }

  public static int right(int i) {
    return 2 * (i + 1);
  }

  public static void maxHeapify(int[] arr, int i, int heapSize) {
    int left = left(i);
    int right = right(i);
    int largest = i;
    if (left < heapSize && arr[left] > arr[largest]) {
      largest = left;
    }
    if (right < heapSize && arr[right] > arr[largest]) {
      largest = right;
    }

    if (largest != i) {
      int temp = arr[i];
      arr[i] = arr[largest];
      arr[largest] = temp;
      maxHeapify(arr, largest, heapSize);
    }
  }

  public static void buildMaxHeap(int[] arr) {
    for (int i = arr.length / 2 - 1; i >= 0; i--) {
      maxHeapify(arr, i, arr.length);
    }
  }

  public static void heapSort(int[] arr) {
    buildMaxHeap(arr);
    for (int i = arr.length - 1; i > 0; i--) {
      int temp = arr[0];
      arr[0] = arr[i];
      arr[i] = temp;
      maxHeapify(arr, 0, i);
    }
  }
}

示例

import java.util.Arrays;

public class Test {
  public static void main(String[] args) {
    int[] arr = {4, 6, 2, 1, 6, 0};
    HeapSortUtils.heapSort(arr);
    System.out.println(Arrays.toString(arr));
  }
}

结果为：

[0, 1, 2, 4, 6, 6]

问题：数组长度与堆大小在代码中用到了，但没有在文字中说明。

优先队列