经典排序算法 - 堆排序Heap sort
堆排序有点小复杂,分成三块
第一块,什么是堆,什么是最大堆
第二块,怎么将堆调整为最大堆,这部分是重点
第三块,堆排序介绍
第一块,什么是堆,什么是最大堆
什么是堆
这里的堆(二叉堆),指得不是堆栈的那个堆,而是一种数据结构。
堆可以视为一棵完全的二叉树,完全二叉树的一个“优秀”的性质是,除了最底层之外,每一层都是满的,这使得堆可以利用数组来表示,每一个结点对应数组中的一个元素.
数组与堆之间的关系
二叉堆一般分为两种：最大堆和最小堆。
什么是最大堆
堆中每个父节点的元素值都大于等于其孩子结点（如果存在）,这样的堆就是一个最大堆
因此,最大堆中的最大元素值出现在根结点(堆顶)
节点与数组索引关系
对于给定的某个结点的下标i，可以很容易的计算出这个结点的父结点、孩子结点的下标，而且计算公式很漂亮很简约
第二块,怎么将堆调整为最大堆,这部分是重点
整个过程如下图所示
在4,14,7这个小堆里边,父节点4小于左孩子14,所以两者交换
在4,2,8这个小堆里边,父节点4小于右孩子8,所以两者交换
上图展示了一趟调整的过程,这个过程递归实现,直到调整为最大堆为止
第三块,堆排序介绍
堆排序就是把堆顶的最大数取出,
将剩余的堆继续调整为最大堆,具体过程在第二块有介绍,以递归实现
剩余部分调整为最大堆后,再次将堆顶的最大数取出,再将剩余部分调整为最大堆,这个过程持续到剩余数只有一个时结束
下边三张图详细描述了整个过程
参考文章
http://blog.kingsamchen.com/archives/547#viewSource
http://www.cnblogs.com/kkun/archive/2011/11/23/2260286.html
相关推荐
堆排序 堆排序（Heap Sort）是一种基于二叉堆数据结构的排序算法
经典排序算法 - 堆排序Heap sort序 经典排序算法 - 地精排序Gnome Sort 经典排序算法 - 奇偶排序Odd-even sort 经典排序算法 - 梳排序Comb sort 经典排序算法 - 耐心排序Patience Sorting 经典排序算法 - 珠...
void heap_sort(int A[],int length) { BUILD_MAX_HEAP(A,length); int i,middle; for(i=length-1;i>0;i--) { middle=A[0]; A[0]=A[i]; A[i]=middle; heap_size--; MAX_HEAPIFY(A,0); } }
堆排序是一种基于比较的排序算法，它通过构造一个大顶堆或小顶堆来实现排序。在C#中实现堆排序，我们可以分为两个主要步骤：建堆和调整堆。这里，我们将深入探讨堆排序的基本原理、C#实现的细节以及其在实际应用中的...
堆排序的核心思想是利用树形数据结构——堆（Heap）来完成排序。堆是一个近似完全二叉树的结构，同时满足大顶堆（父节点的值大于或等于其子节点的值）或小顶堆（父节点的值小于或等于其子节点的值）的性质。在堆排序...
用C++实现的 堆排序，包括恢复堆，构建初始堆
堆排序 1.选择排序 Selection Sort 2.冒泡排序 Bubble Sort 3.插入排序 Insertion Sort 4.归并排序 Merge Sort 5.快速排序 Quick Sort 6.堆排序 Heap Sort 7.总结 summary
它的主要思想是将待排序的序列构造成一个大顶堆（或小顶堆），此时，整个序列的最大值（或最小值）就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值（或最小值）。然后将剩余n-1个元素重新构造成一个...
3. **完整实现**：在C++中，可以使用`make_heap()`函数来创建堆，`pop_heap()`函数来删除堆顶元素并调整堆，`sort_heap()`函数则可以直接完成堆排序。 下面是一个基本的C++实现堆排序的示例代码： ```cpp #include...
最大堆排序（MaxHeap Sort）是一种基于比较的排序算法，它利用了数据结构中的最大堆特性来实现排序。最大堆是一种特殊的二叉堆，每个父节点的值都大于或等于其子节点的值，通常以数组的形式存储。下面将详细介绍最大...
在`堆排序Heap_sort.cpp`中，你可以学习到如何维护堆的性质并进行相应的调整，如 sift-up 和 sift-down 操作，以实现排序。 希尔排序，又称缩小增量排序，是插入排序的一种更高效的改进版本。它通过将待排序的元素...
堆排序算法相对于其他排序算法（如简单选择排序）而言，它能够更有效地处理数据排序问题，尤其适合处理大数据集。 堆排序算法的基本思路是，首先将待排序的数据构建为一个大根堆，这样最大元素就会处于堆顶位置。...
堆排序（Heap Sort）是一种经典的排序算法，它利用堆的数据结构进行排序。堆排序分为两个主要步骤：建堆和排序。 在堆排序中，我们使用最大堆（Max Heap）来进行排序，步骤如下： 建堆：将待排序的序列构造成一个...
堆排序（Heap Sort）是一种基于堆数据结构的比较排序算法。堆是一个近似完全二叉树的结构，并同时满足堆性质：即子节点的键值或索引总是小于（或大于）它的父节点。 在堆排序中，我们主要使用最大堆（Max Heap），...
C++作为一门强大的系统级编程语言，提供了标准模板库（STL），其中的`<algorithm>`头文件包含了各种排序算法，包括heap_sort()函数，可以直接用于堆排序。但在这个项目中，开发者可能选择手动实现堆排序，这样不仅...
C++实现时，可以使用标准库中的`<algorithm>`中的`make_heap`、`pop_heap`和`sort_heap`函数。堆排序在最坏、最好和平均情况下的时间复杂度都是O(n log n)。 4. **快速排序**： 快速排序是C++中最常用的排序算法之...
堆排序算法是计算机科学中用于对一组数进行排序的一种有效算法。它属于选择排序的一种，其思想是先将待排序的序列构造成一个大顶堆，这样堆顶的元素就是最大元素，然后将它与堆数组的末尾元素交换，接着对剩余的n-1...
堆排序（Heap Sort）是一种基于比较的排序算法，它的核心思想是利用二叉堆的数据结构特性来实现排序。本文将详细介绍堆排序的实现步骤、重要概念以及相关操作。 首先，我们要理解什么是堆。堆是一种特殊的树形数据...
在C++中，可以使用标准库中的`std::make_heap`、`std::push_heap`、`std::pop_heap`和`std::sort_heap`等函数来实现堆排序。 **归并排序（Merge Sort）** 归并排序同样采用分治策略。它将数组分为两个子数组，分别...
#### 堆排序 Heap Sort 堆排序是一种基于比较的排序算法，它使用了一种特殊的树形数据结构——堆，通常是一个完全二叉树。 **原理**： - 首先将无序数组构建成一个大顶堆或小顶堆。 - 然后不断取出堆顶元素（即...