排序2

堆排序

• 堆排序是通过完全二叉树实现的

• 堆排序的时间复杂度在所有情况下都是O(nlogn)

• 不稳定的算法

堆

堆是一种数据结构，它是一种特殊的完全二叉树，如果这个堆是一个大顶堆（最大元素在堆顶），那么每个节点上的元素都应该比它子节点上的元素大，最大的元素在根节点上。

__

编号

从根节点开始，每一层从左到右依次编号。将每个元素放到放到同一数组里

             (1)          # 第1行
          /      \
        (2)       (3)
       /  \      /   \
     (4)  (5)  (6)   (7)
    / \  / \   / \   / \ 
             ...
                        \
                      （2^n-1）

因为数组下标从0开始，而堆的编号从1开始，所以数组第一个位置留空

• 父节点为l，则左节点为2l，右节点为2l+1

• 我们编写一个函数，它只用于实现一个功能：给定一个堆，除根节点外所有节点都符合堆性质时，对其根节点向下进行调整，直到堆中所有元素都符合堆的性质