美文网首页
[算法导论]堆排序

[算法导论]堆排序

作者: wenfh2020 | 来源:发表于2019-12-09 05:41 被阅读0次

主要测试大堆,测试源码在(github)


堆可以看成一个近似的完全二叉树,除了底层外,该树是完全充满的,而且是从左到右填充。

完全二叉树适合用数组来存储。用数组来存储完全二叉树是非常节省存储空间的。å

最大堆中,是指除了根结点外(根结点没有 parent),所有结点的 i 都应该满足:
A[PARENT(i)] \ge A[i]

堆数据-数组-二叉树
堆被看作是一个完全二叉树,那么该堆堆高度成正比O(lgn),我们会发现,堆结构上的一些基本操作的运行时间至多与树的高度成正比,即实际复杂度为O(lgn)。

堆排序过程:

MAX-HEAPIFY(堆化):将堆的末端子节点作调整,使得子节点永远小于父节点。
BUILD-MAX-HEAD(建堆):从无序数据数组中构造一个最大堆。
HEAPSORT(排序):对数组进行原址排序,移除位在第一个数据的根节点,并做最大堆调整的递归运算。


堆化

堆化让数值大的结点往上浮,让小的结点逐渐下沉。


堆化流程.png
堆化伪代码
void max_heapify(int array[], int size, int i) {
    int largest = i;
    int l = left(i);
    int r = right(i);

    if (l <= size && array[l] > array[i]) {
        largest = l;
    }

    if (r <= size && array[r] > array[largest]) {
        largest = r;
    }

    if (largest != i) {
        swap(&array[largest], &array[i]);
        max_heapify(array, size, largest);
    }
}

建堆

我们可以通过二叉树结点自底向上的方法,利用堆化过程,把一个大小为 n = A.length 的数组 A = [1...n] 转换为最大堆。BUILD-MAX-HEAP 时间复杂度为 O(n)


建堆伪代码
void build_max_heap(int array[], int len) {
    for (int i = (len / 2); i >= 1; i--) {
        max_heapify(array, len, i);
    }
}

排序

BUILD-MAX-HEAP 会将数组A[1...n]建成最大堆。最大堆元素在根结点A[1],去掉 A[1] 后,A[1]的左右孩子结点仍然是最大堆。如果把 A[n] 替换 A[1],破坏了最大堆性质,将重新对 A[1...n-1] 数组进行堆化,使其变成最大堆。如此递归重复以上步骤。


排序流程
排序流程
void HeapSort::heap_sort() {
    if (m_data_size <= 1) {
        return;
    }

    // 建堆处理后,父结点 > 子结点
    build_max_heap(m_array, m_data_size);
    // 建堆后,堆顶结点(根结点)是最大数值,把最大值放到数组最后。原数组最后一个结点置换到根结点。
    swap(&m_array[1], &m_array[m_data_size]);

    // 排除数组最后一个元素,再对剩余堆进行堆化,再把堆化的根结点放到数组最后。
    m_data_size--;

    // 从上到下(父节点到子树结点)
    while (m_data_size > 1) {
        max_heapify(m_array, m_data_size, 1);
        swap(&m_array[1], &m_array[m_data_size]);
        m_data_size--;
    }
}

优先队列

在计算机系统的作业调度中,任务需要根据优先级进行执行。可以根据堆算法(最大堆),每个任务都赋予一个优先级数值,选出最高优先级(最大堆堆顶)作业任务执行。涉及任务处理,一般都有增删改查的操作。
理解了建堆,堆化和排序的流程,队列的这些操作应该都比较好理解了。


HEAP-MAXINUM

获取堆顶元素,时间复杂度为O(1)

获取堆顶元素
bool HeapSort::heap_maxinum(int& n) {
    if (m_data_size <= 0) {
        return false;
    }
    if (!m_is_build_heap) {
        build_max_heap(m_array, m_data_size);
    }
    n = m_array[1];
    return true;
}

HEAP-EXTRACT-MAX

删除堆顶元素,时间复杂度为O(n)

删除堆顶元素
bool HeapSort::heap_extract_max(int& n) {
    if (m_data_size <= 0) {
        return false;
    }

    if (!m_is_build_heap) {
        build_max_heap(m_array, m_data_size);
    }

    n = m_array[1];
    swap(&m_array[1], &m_array[m_data_size]);
    m_data_size--;
    max_heapify(m_array, m_data_size, 1);
    return true;
}

HEAP-INCREAASE-KEY

增加堆指定元素(任务)的数值,HEAP-INCREAASE-KEY 时间复杂度为O(lgn)

增加数值
bool HeapSort::heap_increase_key(int i, int key) {
    if (i < 1 || m_data_size <= 0 || key < m_array[i]) {
        return false;
    }

    if (!m_is_build_heap) {
        build_max_heap(m_array, m_data_size);
    }

    // 这里跟 build_max_heap 道理一样,只是 build_max_heap
    // 是自底向上,heap_increase_key 是从 i 结点向上
    m_array[i] = key;
    while (parent(i) > 0 && m_array[parent(i)] < m_array[i]) {
        swap(m_array[parent(i)], m_array[i]);
        i = parent(i);
    }
    return true;
}

MAX-HEAP-INSERT

插入新元素到最大堆末位,也就是在最大堆上增加一个叶子,叶子自下而上与它的父结点比较替换。运行时间复杂度为O(lgn)

插入
bool HeapSort::max_heap_insert(int key) {
    if (m_data_size >= m_data_len) {
        return false;
    }

    if (!m_is_build_heap) {
        build_max_heap(m_array, m_data_size);
    }

    // 将结点放置数组末位,也就是在最大堆上增加一个叶子,叶子自下而上与它的父结点比较替换。
    m_data_size++;
    m_array[m_data_size] = key;

    // 这是 heap_increase_key 主逻辑的实现。
    int i = m_data_size;
    while (parent(i) > 0 && m_array[parent(i)] < m_array[i]) {
        swap(m_array[parent(i)], m_array[i]);
        i = parent(i);
    }

    return true;
}

参考

现在发现,单纯看《算法导论》很难看懂文章内容,可以先从其它的帖子中理解算法的逻辑,在对算法有一定的理解的基础上,再结合书本内容,才能更好理解书本内容。


wiki
《算法导论》第六章 堆排序
堆和堆排序:为什么说堆排序没有快速排序快


更精彩内容,请关注我的博客:https://wenfh2020.com

相关文章

  • 堆排序HeapSort

    引用算法导论中对于堆排序的描述: Like merge sort,but unlike insertion sor...

  • [算法导论]堆排序

    主要测试大堆,测试源码在(github) 堆 堆可以看成一个近似的完全二叉树,除了底层外,该树是完全充满的,而且是...

  • 堆排序

    阅读经典——《算法导论》05 本文介绍一种神奇的排序方法:堆排序。 堆排序不像插入排序和归并排序那样直观,它利用了...

  • 计数排序、基数排序和桶排序

    阅读经典——《算法导论》07 到目前为止,我们已经介绍了插入排序、归并排序、堆排序、快速排序这四种排序算法,他们的...

  • iOS算法总结-堆排序

    iOS算法总结-堆排序 iOS算法总结-堆排序

  • 算法导论第6.4章 - 堆排序算法

    伪代码利用了维护堆和建立堆的部分 堆排序 建立堆 维护堆的性质 在建立好的堆里面,根部的元素是最大的,然后把这个最...

  • 浅谈排序算法

    前段时间在看计算机科学科学及编程导论,其中谈到了排序的各种算法,在这我浅谈四种插入,选择,冒泡,以及堆排序。 首先...

  • 算法导论学习001-堆排序

    堆排序 堆排序基本简介 1991年的计算机先驱奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德(Robert ...

  • 数据结构与算法

    常见排序算法 堆排序 算法大全 算法大汇总

  • 堆排序算法思想

    前两天看了看堆排序算法,啃了半天的书,最后搞明白了堆排序算法,今天有时间给大家说说这个堆排序算法。首先讲一下算法的...

网友评论

      本文标题:[算法导论]堆排序

      本文链接:https://www.haomeiwen.com/subject/ebqmgctx.html