美文网首页算法札记Android知识Android开发
常用排序算法总结7一一堆排序

常用排序算法总结7一一堆排序

作者: craneyuan | 来源:发表于2016-09-03 21:30 被阅读115次

在了解堆排序之前,我们有必要清楚“什么是堆呢?”。

堆(英语:Heap)是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵树的数组对象。在队列中,调度程序反复提取队列中第一个作业并运行,因为实际情况中某些时间较短的任务将等待很长时间才能结束,或者某些不短小,但具有重要性的作业,同样应当具有优先权。堆即为解决此类问题设计的一种数据结构。

堆的逻辑定义:


堆的逻辑定义

堆的实现通过构造二叉堆(英语:binary heap),实为二叉树的一种;由于其应用的普遍性,当不加限定时,均指该数据结构的这种实现。这种数据结构具有以下性质。

  • 任意节点小于(或大于)它的所有后裔,最小元(或最大元)在堆的根上(堆序性)。
  • 堆总是一棵完全树。即除了最底层,其他层的节点都被元素填满,且最底层尽可能地从左到右填入。

将根节点最大的堆叫做最大堆或大根堆,根节点最小的堆叫做最小堆或小根堆。常见的堆有二叉堆、斐波那契堆等。

定义

堆排序(英语:Heap Sort)是指利用这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。

堆排序演示动画

算法步骤

堆排序的根本是进行一次堆的构建过程。

  • 得到当前序列的最小(大)的元素
  • 把这个元素和最后一个元素进行交换,这样当前的最小(大)的元素就放在了序列的最后,而原先的最后一个元素放到了序列的最前面
  • 这交换可能会破坏堆序列的性质(注意此时的序列是除去已经放在最后面的元素),因此需要对序列进行调整,使之满足于上面堆的性质
  • 重复上面的过程,直到序列调整完毕为止

堆的操作

在堆的数据结构中,堆中的最大值总是位于根节点。堆中定义以下几种操作:

  • 最大堆调整(Max_Heapify):将堆的末端子节点作调整,使得子节点永远小于父节点
  • 创建最大堆(Build_Max_Heap):将堆所有数据重新排序
  • 堆排序(HeapSort):移除位在第一个数据的根节点,并做最大堆调整的递归运算

堆节点的访问

通常堆是通过一维数组来实现的。在数组起始位置为0的情形中:

  • 父节点i的左子节点在位置(2*i+1);
  • 父节点i的右子节点在位置(2*i+2);
  • 子节点i的父节点在位置floor((i-1)/2);

代码实现(java)

/**
 *
 * @Title: heapSort
 * @Description: 堆排序的简单实现
 * @param: @param a
 * @return: void
 * @throws
 */
public static void heapSort(int[] a)
{
    int count = a.length;

    // first place a in max-heap order
    heapify(a, count);

    int end = count - 1;
    while (end > 0) {
        // swap the root(maximum value) of the heap with the
        // last element of the heap
        int tmp = a[end];
        a[end] = a[0];
        a[0] = tmp;
        // put the heap back in max-heap order
        siftDown(a, 0, end - 1);
        // decrement the size of the heap so that the previous
        // max value will stay in its proper place
        end--;
    }
}

private static void heapify(int[] a, int count)
{
    // start is assigned the index in a of the last parent node
    int start = (count - 2) / 2; // binary heap

    while (start >= 0) {
        // sift down the node at index start to the proper place
        // such that all nodes below the start index are in heap
        // order
        siftDown(a, start, count - 1);
        start--;
    }
    // after sifting down the root all nodes/elements are in heap order
}

private static void siftDown(int[] a, int start, int end)
{
    // end represents the limit of how far down the heap to sift
    int root = start;

    while ((root * 2 + 1) <= end) { // While the root has at least one child
        int child = root * 2 + 1; // root*2+1 points to the left child
        // if the child has a sibling and the child's value is less than its
        // sibling's...
        if (child + 1 <= end && a[child] < a[child + 1])
            child = child + 1; // ... then point to the right child instead
        if (a[root] < a[child]) { // out of max-heap order
            int tmp = a[root];
            a[root] = a[child];
            a[child] = tmp;
            root = child; // repeat to continue sifting down the child now
        } else
            return;
    }
}

参考文章

相关文章

  • iOS算法总结-堆排序

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

  • 常用的排序算法

    常用的排序算法 常用的排序算法插入排序折半插入排序shell 排序冒泡排序选择排序快速排序基数排序归并排序堆排序K...

  • 排序算法

    一、排序算法总结 排序算法题目 排序算法快速排序堆排序归并排序 应用最小K个数(TopK问题)215.数组中的第K...

  • 排序算法

    排序算法分类 排序算法常用主要有:冒泡排序法、快速排序法、选择排序法、插入排序法、堆排序法、归并排序法等几种。 ...

  • 堆排序

    转载:图解排序算法(三)之堆排序 预备知识 堆排序 堆排序是利用堆这种数据结构而设计的一种排序算法,堆排序是一种选...

  • 排序算法-堆排序

    参考: Java排序算法(五):堆排序 【算法与数据结构】图说堆排序 【数据结构】排序算法:希尔、归并、快速、堆排...

  • 数据结构与算法

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

  • 数据结构

    Q:堆排序 A:1 堆排序算法(图解详细流程)2 堆排序 Q:排序算法时间复杂度与稳定性 选择排序为什么不稳定:举...

  • 算法

    1.常用的八个基本排序算法 -前言:希尔排序和直接插入排序属于插入排序算法,简单选择排序和堆排序属于选择排序,冒泡...

  • 排序算法总结(JAVA版)

    简介:本文主要总结了以下几个排序算法:冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序、堆排序、计数排序...

网友评论

    本文标题:常用排序算法总结7一一堆排序

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