FunctionGHW

立志成为真正程序员的码农,伪全栈,目前主要写C#

堆排序(Heap Sort)算法学习

FunctionGHW posted @ 2013年10月29日 21:54 in 算法学习 with tags 排序 in-place heap sort max heap , 6491 阅读

堆排序可以看作选择排序的进化版。选择排序通过遍历来选出最大(最小)元素, 堆排序利用数据结构二叉堆更快的选出最大(最小)元素。堆排序有两个优势: 1.)最好、最坏和平均时间复杂度均为\(O(nlogn)\); 2.)可以原地进行,空间复杂度\(O(1)\)。

最大(最小)堆的性质

二叉堆通常是一个数组, 可以被看作完全(或近似完全)二叉树。

  • 一个二叉堆是最大堆,则满足如下条件:
    对任意的节点 \(i\),如果存在父节点\(parent(i)\),则必有\(parent(i) \ge i\)。
  • 一个二叉堆是最小堆,则满足如下条件:
    对任意的节点 \(i\),如果存在父节点\(parent(i)\),则必有\(parent(i) \le i\)。

由最大(小)堆的性质不难推出: 最大(小)值在树的根上。

堆排序算法

堆排序的基本思路如下:

  1. 把待排序数组构造成一个最大堆
  2. 取出树的根(最大(小)值, 实际算法的实现并不是真正的取出)
  3. 将树中剩下的元素再构造成一个最大堆(这里的构造和第1步不一样,具体看实现部分)
  4. 重复2,3操作,直到取完所有的元素
  5. 把元素按取出的顺序排列,即得到一个有序数组(在代码实现里是通过交换操作"无形中"完成的)
在开始实现算法先看几个结论(证明略):
  • 完全二叉树A[0:n-1]中的任意节点,其下标为 \(i\), 那么其子节点的下标分别是为\(2i + 1\) 和 \(2(i + 1)\)
  • 大小为n的完全二叉树A[0:n-1],叶子节点中下标最小的是\(\lfloor \frac {n}{2} \rfloor\), 非叶子节点中下标最大的是\(\lfloor \frac {n}{2} \rfloor - 1\)
  • 如果数组是一个最大堆,那么最大元素就是A[0]
  • 最大堆中任意节点的左右子树也是最大堆

 

这里的算法实现使用的是最大堆,首先来解决由数组建立最大堆的问题:

// 用于计算下标为i的节点的两个子节点的下标值
#define LEFT(i) (2 * (i) + 1)
#define RIGHT(i) (2 * ((i) + 1))
                
/* 此函数把一颗二叉树中以node为根的子树变成最大堆。
 * 注意: 使用的前提条件是 node节点的左右子树(如果存在的话)都是最大堆。
 * 这个函数是整个算法的关键。
 */
void max_heapify(int heap[], int heap_size, int node)
{
    // 这里先不考虑整数溢出的问题
    // 先把注意力放在主要的功能上
    // 如果数据规模够大,int类型必然会溢出
    int l_child = LEFT(node);
    int r_child = RIGHT(node);
    int max_value = node;

    if (l_child < heap_size && heap[l_child] > heap[max_value])
    {
        max_value = l_child;
    }
    if (r_child < heap_size && heap[r_child] > heap[max_value])
    {
        max_value = r_child;
    }
    if (max_value != node)
    {
        swap_val(heap + node, heap + max_value);

        // 之后还要保证被交换的子节点构成的子树仍然是最大堆
        // 如果不是这个节点会继续"下沉",直到合适的位置
        max_heapify(heap, heap_size, max_value);
    }
}

/* 将一个数组构造成最大堆
 * 自底向上的利用max_heapify函数处理
 */
void build_max_heap(int heap[], int heap_size)
{
    if (heap_size < 2)
    {
        return;
    }
    int first_leaf = heap_size >> 1;//第一个叶子节点的下标

    int i;
    // 从最后一个非叶子节点开始自底向上构建,
    // 叶子节点都看作最大堆,因此可以使用max_heapify函数
    for (i = first_leaf - 1; i >= 0; i--)
    {
        max_heapify(heap, heap_size, i);
    }
}
                

函数max_heapify将指定子树的根节点"下沉"到合适的位置, 最终子树变成最大堆, 该过程最坏时间复杂度为\(O(\log n)\)。函数build_max_heap自底向上的调用max_heapify, 最终整个数组满足最大堆,迭代过程的复杂度为\(O(n\log n)\), 因此整个函数的最坏时间复杂度也是\(O(n\log n)\)。 而如果当前数组已经是最大堆了,例如数组原本是降序排列的, 那么max_heapify过程的时间复杂度就是\(O(1)\), 此时build_max_heap的时间复杂度是\(O(n)\),这是最好的情况。

接着实现堆排序过程:

/* heap sort 主函数
 */
void heap_sort(int heap[], int heap_size)
{
    if (heap == NULL || heap_size < 2)
    {
        return;
    }
    //构建最大堆
    build_max_heap(heap, heap_size);

    int i;
    for (i = heap_size - 1; i > 0; i--)
    {
        /* 把当前树的根节点交换到末尾
         * 相当于取出最大值,树的规模变小。
         * 交换后的树不是最大堆,但是根的两颗子树依然是最大堆
         * 满足调用max_heapify的条件。之所以这样交换,
         * 是因为用max_heapify处理时间复杂度较低,
         * 如果不交换而直接"取出"heap[0], 此处可能要使用
         * build_max_heap重新建立最大堆,时间复杂度较大
         */
        swap_val(heap, heap + i);

        heap_size--;
        //维护最大堆
        max_heapify(heap, heap_size, 0);
    }
}
                

最终的堆排序算法中,build_max_heap的复杂度是已知的, 迭代部分和build_max_heap的实现类似,而且不难看出, 交换后的根元素在下一次建堆过程中必然下沉到堆底,因此无论情况好坏, 该迭代过程时间复杂度都是\(O(n\log n)\), 所以整个算法的最好最坏和平均时间复杂度都是\(O(n\log n)\)。

堆排序算法的空间复杂度是\(O(1)\),从实现上很容易看出来。


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter