目前接触的一些思路：滑动窗口、动态规划、贪心、斐波那契、二分法、递归、前/中/后序/层序（辅助队列）遍历、DFS（深度优先遍历）、BFS（广度优先遍历）

昨天在剑指-41 数据流中的中位数中看到了两种思路解题

• 大顶堆和小顶堆找出中位数
• 通过有序集合和两个指针来指向中位数所在地址（因为元素数目存在奇数和偶数的情况）

大顶堆和小顶堆的思路比较有趣，因为这个思路以前常听但是没有深入了解。常用用途：排序，优先队列 PriorityQueue

堆排序虽然名字是堆，但是并不是Java虚拟机模型中的堆，而是根据二叉树特性构造的数组(该二叉树除了最后一层不一定满，其他各层都是满节点的，因为数组中的元素映射到堆中是从上到下，从左到右的)

数组 heap
｜1｜2｜3｜4｜5｜6｜
      1
     / \
    2   3
   / \ /
  4  5 6 
下标为i（这里为了方便对齐，下标从1开始）的元素父节点，左节点，右节点下标可以分别表示为
父节点 =》i/2
左节点 =》2i
右节点 =》2i+1

大顶堆/小顶堆定义，堆顶元素为最大/最小值（注意，这不代表整个数组中的元素是完全有序的，只保证堆顶元素的最大/最小性质）

基础的堆排序分可以拆分成两步实现

• 构造最大/最小堆
• 循环以下步骤
  • 交换数组首元素和最后一个元素
  • 重构交换元素后的堆

构造堆的步骤

• 从数组的length/2～0循环进行堆化
• 堆化步骤
  • 判断根节点和左右节点的大小，如果不符合定义则进行元素值交换
  • 如果产生了交换，则递归堆化子数，使其仍符合堆定义

以下给出大小顶堆以及堆排序的实现

    /**
   * 堆排序
   *
   * @param nums 待排序数组
   * @param ascOrder true 升序 false 降序
   */
  public static void heapSort(int[] nums, boolean ascOrder) {
    for (int i = nums.length - 1; i > 0; i--) {
      buildHeap(nums, i, ascOrder);
      swap(nums, 0, i);
    }
  }

  /**
   * 数据交换
   * @param nums 数组
   * @param a 下标1
   * @param b 下标2
   */
  private static void swap(int[] nums, int a, int b) {
    int tmp = nums[a];
    nums[a] = nums[b];
    nums[b] = tmp;
  }

  /**
   * 建堆
   *
   * @param nums 数组
   */
  private static void buildHeap(int[] nums, int heapSize, boolean maxHeapPify) {
    int index = heapSize / 2;
    // 必须自底向上进行堆化，确保整个堆一定符合定义，避免前面的元素堆化后，后面出现大于堆顶的元素导致堆化失败。类似于冒泡排序的思想，必须让最大值从下到上浮
    while (index >= 0) {
      heapPify(nums, heapSize, index, maxHeapPify);
      index--;
    }
  }

  /**
   * 堆化
   *
   * @param nums 数组
   * @param heapSize 堆有效边界
   * @param index 要堆化的根节点下标
   * @param maxHeapPify true - 最大堆 false - 最小堆
   */
  private static void heapPify(int[] nums, int heapSize, int index, boolean maxHeapPify) {
    /* 
      1.比较根节点和左右两个子节点下标的大小，如果不符合堆排性质，则调整
      2.如果根节点和左右节点进行了调换，那么要递归调用该子树堆化
    */
    int left = getLeft(index);
    int right = getRight(index);
    // 最大值下标
    int largest = index;
    if (left <= heapSize) {
      if (maxHeapPify) {
        // 大顶堆
        if (nums[left] > nums[largest]) {
          largest = left;
        }
      } else {
        // 小顶堆
        if (nums[left] < nums[largest]) {
          largest = left;
        }
      }
    }
    if (right <= heapSize) {
      if (maxHeapPify) {
        // 大顶堆
        if (nums[right] > nums[largest]) {
          largest = right;
        }
      } else {
        // 小顶堆
        if (nums[right] < nums[largest]) {
          largest = right;
        }
      }
    }
    if (largest != index) {
      // 交换元素值
      swap(nums, index, largest);
      // 递归重新堆化该子树
      heapPify(nums, heapSize, largest, maxHeapPify);
    }
  }

  /**
   * 获取左子节点下标，下标从0开始
   *
   * @param parent 父节点下标
   * @return 左节点下标
   */
  private static int getLeft(int parent) {
    return 2 * parent + 1;
  }

  /**
   * 获取右节点下标,下标从0开始
   *
   * @param parent 父节点下标
   * @return 右节点下标
   */
  private static int getRight(int parent) {
    return 2 * parent + 2;
  }

Q.E.D.