堆排序

还想看更多文章的朋友可以访问我的个人博客

一些基础知识

学习堆排序，总要了解堆的数据结构吧，了解堆又需要了解二叉树的基本知识，了解二叉树要先知道树是个什么东西吧…… 呃，还是太年轻。这里简单谈谈吧。

二叉树

提一下树——树是一对多的数据结构，从一个根结点开始，生长出它的子结点，而每一个子结点又生长出各自的子结点，成为子树。如果某个结点不再生长出子结点了，它就成为叶子。

一个普通的树结构
二叉树是每个节点最多有两个子树（）的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree），且次序不能颠倒。

二叉树
完全二叉树除最后一层外，若其余层都是满的，并且最后一层或者是满的，或者是在右边缺少连续若干节点。

完全二叉树

满二叉树的所有分支结点都既有左子树又有右子树，并且所有叶子都在同一层。每一层上的节点数都是最大节点数。

满二叉树

数组与堆结构（如何用数组实现）：

image

对于任一节点（若其在数组中对应元素下标为 i）而言，都有
- 子节点：左孩子是2*i+1，右孩子是2*i+2
- 父节点：(i - 1) / 2

生成大根堆：

堆可以分为大根堆和小根堆。在大根堆中，所有子树中子节点的值都小于等于父节点；而小根堆的组织方式恰好相反：所有子树中子节点的值都大于等于父节点。在堆排序中，使用的是大根堆；而小根堆常被用作构建优先队列。

调整大根堆的过程，遍历数组元素，将当前节点与其父节点进行比较：

若当前节点小于等于父节点，则比较下一位置。
若当前节点大于父节点，则将当前节点与父节点交换，然后比较交换后的父节点（交换前的“当前”节点）与其父节点进行比较(交换）过程。这个过程很明显可以是个递归过程。

下面是该过程的实现：

      /**
        * 递归调整大根堆
        * @param arr array
        * @param index current node index
        * @param comparable 比较原则
        */
      private void heapInsert(T[] arr, int index, Comparator<T> comparable) {
          int parent = (index - 1) >>> 1;
          if (comparable.compare(arr[index], arr[parent]) <= 0) {
              return;
          }

          swap(arr, index, parent);
          heapInsert(arr, parent, comparable);
      }

      /**
        * 非递归调整大根堆
        */
      private void heapInsertByLoop(T[] arr, int index, MangoComparable<T> comparable) {
          int parent = (index - 1) / 2;
          while (comparable.compare(arr[index], arr[parent]) > 0) {
              swap(arr, index, parent);
              index = parent;
              parent = (index - 1) / 2;
          }
      }

容易想到的是，调整完毕后的树仍然是无序的。但是可以理解的是根节点一定是整个树（数组）的最大值，那么我们完全可以利用上述过程查找最大值，然后将与树的最后一个节点交换。再对除最后一个节点的前n-1个树节点（将树的规模缩小1，size--）进行大根堆调整，再交换。循环执行此过程，即可使得元素升序排列。

值得注意的是，大根堆生成过程中的调整策略，是将当前元素与父节点比较（由底向上），利用该策略同样可以完成上述排序过程，流程如下：(构建大根堆 -> 交换)

image

具体实现如下：


    @Override
    public void sort(T[] array, Comparator<T> comparable) {
        if (array == null || array.length < 2) {
            return;
        }

        for (int i = 0; i < array.length; i++) {
            heapInsert(array, i, comparable);
        }

        int heapSize = array.length;
        swap(array, 0, --heapSize);

        while (heapSize > 0) {
            for (int i = 0; i < heapSize; i++) {
                heapInsert(array, i, comparable);
            }
            swap(array, 0, --heapSize);
        }
    }

而在排序过程中，我们当然也可以便利地比较左右子树与父节点即，当前节点（由顶向下，毕竟此时我们已经生成了堆结构了）。找到当前节点的左右节点中较大的子节点，与当前节点比较：

若当前节点大于等于较大的子节点，则判断下一个节点。
若当前节点小于较大的子节点，则将当前节点与较大的节点交换（我们的目标是让最大值向上浮）。然后比较交换后的所产生的父节点（交换前的较大的子节点）与其子节点进行比较(交换）。

具体流程如下：

image

具体实现如下：

 @Override
    public void sort(T[] array, Comparator<T> comparable) {
        // ...
        while (heapSize > 0) {
            heapify(array, 0, heapSize, comparable);
        }
    }

    /**
     * 递归版
     */
    private void heapify(T[] arr, int index, int size, Comparator<T> comparable) {
        int left = 2*index + 1;
        if (left < size) {
            int largestChild = left + 1 < size 
                && comparable.compare(arr[left+1], arr[left]) > 0 ? left+1 : left;
            if (comparable.compare(arr[largestChild], arr[index]) < 0) {
                return;
            }

            swap(arr, largestChild, index);
            heapify(arr, largestChild, size, comparable);
        }
    }

 /**
     * 非递归版
     */
   private void heapifyByLoop(T[] arr, int index, int size, Comparator<T> comparable) {
        int left = 2*index + 1;
        while (left < size) {
            int largestChild = left + 1 < size 
                && comparable.compare(arr[left+1], arr[left]) > 0 ? left+1 : left;
            if (comparable.compare(arr[largestChild], arr[index]) < 0) {
                return;
            }

            swap(arr, largestChild, index);
            index = largestChild;
            left = 2*index + 1;
        }
    }

时间复杂度分析：我们知道二叉树结构的基础操作时间复杂度为O(logN)，其中N是树的节点数。大根堆的生成过程相当于不断向树中增加节点的过程，即
```
数组中下标为0的元素，插入高度为0的二叉树；
数组中下标为1的元素，插入高度为1的二叉树；
数组中下标为2的元素，插入高度为2的二叉树；
……
数组中下标为n-1的元素，插入高度为n-1的二叉树；
```
所以，该操作时间复杂度为 $O(log1 + log2 + ... + logi + ... + logn) = O(logn!)$ ，经数学证明（ $logn!$ 和 $nlogn$ "同阶函数"），因此生成大根堆的时间复杂度是O(nlogn)。

堆排序

一些基础知识

二叉树

堆排序

推荐阅读更多精彩内容