Lqsss's Blog
0%

堆排序

Posted on In
Symbols count in article: 1.4k Reading time ≈ 1 mins.

堆排序介绍和相关代码

什么叫堆

满二叉树、完全二叉树

  • 满二叉树：一棵深度为 k，且有 2的k次方 - 1 个节点称之为满二叉树
  • 完全二叉树：深度为k，有n个节点的二叉树，当且仅当其每一个节点都与深度为 k 的满二叉树中序号为 1 至 n 的节点对应时，称之为完全二叉树

堆

堆（二叉堆）可以视为一棵完全的二叉树，除了最底层，其他每一层都是满的。因此可以用数组来储存。

  • Parent(i) = floor(i/2)，i 的父节点下标
  • Left(i) = 2i，i 的左子节点下标
  • Right(i) = 2i + 1，i 的右子节点下标

二叉堆分类

  • 最大堆：堆顶元素最大，下面的子结构的父节点元素比左右子节点元素大于或等于
  • 最小堆：堆顶元素最小，下面的子结构的父节点元素比左右子节点元素小于或等于

堆排序

思想：

  1. 构成最大堆
  2. 取出栈顶元素
  3. 重新将剩下元素构成最大堆
  4. 反复此过程，直到最后一个元素

代码

  • sort

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    //堆排序入口
    public void sort(int[] array) {
        //构建最大堆
        buildMaxHeep(array);
        //进行沉淀
        for (int i = array.length - 1; i > 0; i--) {
            swap(array, i, 0); //交换最大堆顶和堆底
            maxHeap(array, i, 0); //重新对0->i进行最大堆
        }
    }

  • 构建最大堆

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    private void buildMaxHeep(int[] array) {
        if (array == null || array.length <= 1) {
            return;
        }
        //从中间往前开始遍历，结构稳定
        int half = (array.length - 1) / 2;
        for (int i = half; i >= 0; i--) {
            maxHeap(array, array.length, i);  //递归：比较交换
        }
    }

Q：为什么从中间开始往前调整，可以完成整个二叉堆到最大堆的工作？

A：层数为k（深度）的一层没有子节点，不需要判断是否是满足最大堆的结构

  • 调整最大堆
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    private void maxHeap(int[] array, int length, int i) {
         int left = i * 2 + 1;
         int right = i * 2 + 2;
         int maxNode = i;

         if (left <length&&array[left] > array[i] ) {
             maxNode = left;
         }
         if (right < length&&array[right] > array[maxNode] ) {
             maxNode = right;
         }
         if (maxNode != i) {
             //说明左右子节点比当前i节点大
             //swap
             swap(array, i, maxNode);
             maxHeap(array, length, maxNode); //继续递归maxNode，跟它的下面比较
         }

     }