【坐在马桶上看算法】算法12：堆——神奇的优先队列(下)汇总
- 格式：docx
- 大小：230.14 KB
- 文档页数：16
文档推荐
-
座便器成品检验标准页数:4
-
上厕所的正确姿势页数:1
-
都你怎样正确使用马桶页数:3
-
怎样辨别马桶质量好坏页数:5
-
马桶使用注意事项页数:3
-
马桶卫生坐垫用纸项目分析页数:3
下载文档原格式
合集下载
头歌数据结构十大经典排序算法 -回复
头歌数据结构十大经典排序算法-回复什么是经典排序算法？经典排序算法是指在计算机科学领域中被广泛应用和研究的排序算法。
排序是计算机科学中的基本操作之一，它的目标是将一组元素按照某种特定的顺序进行排列。
经典排序算法通常被用来解决排序问题，可以应用于数据的排序、搜索、统计等各种计算任务中。
在这篇文章中，我们将讨论头歌数据结构中的十大经典排序算法，探索每个算法的原理和实现方法，以及它们的优缺点和适用场景。
1. 冒泡排序（Bubble sort）冒泡排序是一种简单直观的排序算法，它的基本思想是重复地交换相邻两个元素，将较大的元素逐渐“浮”到数组的尾部。
具体实现可以使用两层嵌套循环，外层循环控制比较的轮数，内层循环进行元素比较和交换。
冒泡排序的时间复杂度为O(n^2)。
2. 选择排序（Selection sort）选择排序是一种简单的选择最小元素的排序算法，它的基本思想是从头开始，逐个选择最小的元素，并将其放置到已排序部分的末尾。
具体实现可以使用两层嵌套循环，外层循环控制已排序部分的末尾位置，内层循环用于选择最小元素。
选择排序的时间复杂度为O(n^2)。
3. 插入排序（Insertion sort）插入排序是一种简单直观的排序算法，它的基本思想是将已排序部分的元素依次与未排序部分的元素进行比较并插入到正确的位置。
具体实现可以使用两层嵌套循环，外层循环控制未排序部分的元素，内层循环用于比较和插入元素。
插入排序的时间复杂度为O(n^2)。
4. 希尔排序（Shell sort）希尔排序是一种改进的插入排序算法，它的基本思想是将数组划分为若干个子序列，并分别对子序列进行插入排序，直到整个数组有序。
具体实现使用增量序列来控制子序列的划分和插入排序的间隔，最终将整个数组排序。
希尔排序的时间复杂度为O(nlogn)。
5. 归并排序（Merge sort）归并排序是一种分治法排序算法，它的基本思想是将数组分成两个子数组，分别对子数组进行递归排序，然后将排序好的子数组合并成一个有序的数组。
广度优先和深度优先的例子
广度优先和深度优先的例子广度优先搜索(BFS)和深度优先搜索(DFS)是图遍历中常用的两种算法。
它们在解决许多问题时都能提供有效的解决方案。
本文将分别介绍广度优先搜索和深度优先搜索，并给出各自的应用例子。
一、广度优先搜索(BFS)广度优先搜索是一种遍历或搜索图的算法，它从起始节点开始，逐层扩展，先访问起始节点的所有邻居节点，再依次访问其邻居节点的邻居节点，直到遍历完所有节点或找到目标节点。
例子1：迷宫问题假设有一个迷宫，迷宫中有多个房间，每个房间有四个相邻的房间：上、下、左、右。
现在我们需要找到从起始房间到目标房间的最短路径。
可以使用广度优先搜索算法来解决这个问题。
例子2：社交网络中的好友推荐在社交网络中，我们希望给用户推荐可能认识的新朋友。
可以使用广度优先搜索算法从用户的好友列表开始，逐层扩展，找到可能认识的新朋友。
例子3：网页爬虫网页爬虫是搜索引擎抓取网页的重要工具。
爬虫可以使用广度优先搜索算法从一个网页开始，逐层扩展，找到所有相关的网页并进行抓取。
例子4：图的最短路径在图中，我们希望找到两个节点之间的最短路径。
可以使用广度优先搜索算法从起始节点开始，逐层扩展，直到找到目标节点。
例子5：推荐系统在推荐系统中，我们希望给用户推荐可能感兴趣的物品。
可以使用广度优先搜索算法从用户喜欢的物品开始，逐层扩展，找到可能感兴趣的其他物品。
二、深度优先搜索(DFS)深度优先搜索是一种遍历或搜索图的算法，它从起始节点开始，沿着一条路径一直走到底，直到不能再继续下去为止，然后回溯到上一个节点，继续探索其他路径。
例子1：二叉树的遍历在二叉树中，深度优先搜索算法可以用来实现前序遍历、中序遍历和后序遍历。
通过深度优先搜索算法，我们可以按照不同的遍历顺序找到二叉树中所有节点。
例子2：回溯算法回溯算法是一种通过深度优先搜索的方式，在问题的解空间中搜索所有可能的解的算法。
回溯算法常用于解决组合问题、排列问题和子集问题。
例子3：拓扑排序拓扑排序是一种对有向无环图(DAG)进行排序的算法。
排序算法十大经典方法
排序算法十大经典方法
排序算法是计算机科学中的经典问题之一，它们用于将一组元素按照一定规则排序。
以下是十大经典排序算法：
1. 冒泡排序：比较相邻元素并交换，每一轮将最大的元素移动到最后。
2. 选择排序：每一轮选出未排序部分中最小的元素，并将其放在已排序部分的末尾。
3. 插入排序：将未排序部分的第一个元素插入到已排序部分的合适位置。
4. 希尔排序：改进的插入排序，将数据分组排序，最终合并排序。
5. 归并排序：将序列拆分成子序列，分别排序后合并，递归完成。
6. 快速排序：选定一个基准值，将小于基准值的元素放在左边，大于基准值的元素放在右边，递归排序。
7. 堆排序：将序列构建成一个堆，然后一次将堆顶元素取出并调整堆。
8. 计数排序：统计每个元素出现的次数，再按照元素大小输出。
9. 桶排序：将数据分到一个或多个桶中，对每个桶进行排序，最后输出。
10. 基数排序：按照元素的位数从低到高进行排序，每次排序只考虑一位。
以上是十大经典排序算法，每个算法都有其优缺点和适用场景，选择合适的算法可以提高排序效率。
十大经典排序算法（动图演示）
⼗⼤经典排序算法（动图演⽰）0、算法概述0.1 算法分类⼗种常见排序算法可以分为两⼤类：⽐较类排序：通过⽐较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此也称为⾮线性时间⽐较类排序。
⾮⽐较类排序：不通过⽐较来决定元素间的相对次序，它可以突破基于⽐较排序的时间下界，以线性时间运⾏，因此也称为线性时间⾮⽐较类排序。
0.2 算法复杂度0.3 相关概念稳定：如果a原本在b前⾯，⽽a=b，排序之后a仍然在b的前⾯。
不稳定：如果a原本在b的前⾯，⽽a=b，排序之后 a 可能会出现在 b 的后⾯。
时间复杂度：对排序数据的总的操作次数。
反映当n变化时，操作次数呈现什么规律。
空间复杂度：是指算法在计算机内执⾏时所需存储空间的度量，它也是数据规模n的函数。
1、冒泡排序（Bubble Sort）冒泡排序是⼀种简单的排序算法。
它重复地⾛访过要排序的数列，⼀次⽐较两个元素，如果它们的顺序错误就把它们交换过来。
⾛访数列的⼯作是重复地进⾏直到没有再需要交换，也就是说该数列已经排序完成。
这个算法的名字由来是因为越⼩的元素会经由交换慢慢“浮”到数列的顶端。
1.1 算法描述⽐较相邻的元素。
如果第⼀个⽐第⼆个⼤，就交换它们两个；对每⼀对相邻元素作同样的⼯作，从开始第⼀对到结尾的最后⼀对，这样在最后的元素应该会是最⼤的数；针对所有的元素重复以上的步骤，除了最后⼀个；重复步骤1~3，直到排序完成。
1.2 动图演⽰1.3 代码实现function bubbleSort(arr) {var len = arr.length;for (var i = 0; i < len - 1; i++) {for (var j = 0; j < len - 1 - i; j++) {if (arr[j] > arr[j+1]) { // 相邻元素两两对⽐var temp = arr[j+1]; // 元素交换arr[j+1] = arr[j];arr[j] = temp;}}}return arr;}2、选择排序（Selection Sort）选择排序(Selection-sort)是⼀种简单直观的排序算法。
2024王导数据结构综合应用题
2024王导数据结构综合应用题假设2024年，王导是一位深受学生喜爱的计算机科学导师。
他设计了一道综合应用题，旨在考察学生对数据结构的应用能力。
以下是题目内容和解答。
题目：在2024年的某个国家，有许多城市需要进行道路规划。
每个城市可以通过道路连接到其他城市，形成一个网络。
现有一份城市之间的道路连接关系表，其中包含了城市之间可以直接通行的道路及其长度。
请设计一个算法，找到所有城市之间的最短路径及其长度。
解答：为了解决这个问题，我们可以使用图的最短路径算法。
以下是一种常用的算法——Dijkstra算法。
1. 创建一个集合S，用于存放已经找到最短路径的城市，初始时为空。
2. 创建一个数组dist，用于存放每个城市到起点的最短路径长度，初始时所有元素为无穷大。
3. 选取一个起点，设置dist[起点]为0，并将起点加入集合S。
4. 对于起点相邻的每个城市，更新其到起点的最短路径长度，并将其加入集合S。
5. 从剩余的城市中选取一个离起点最近的城市u，将它加入集合S。
6. 对于每个城市v，如果v不在集合S中且通过u可以找到更短的路径，则更新其最短路径长度，并将其加入集合S。
7. 重复步骤5和步骤6，直到所有城市都加入集合S。
使用Dijkstra算法可以找到起点到所有城市的最短路径及其长度。
在这里可以使用优先队列（最小堆）来存储城市和最短路径长度的对应关系，以提高算法效率。
接下来我们以一个具体的例子来说明算法的步骤。
假设有4个城市，用数字1、2、3、4代表，它们之间的道路如下：- 城市1和城市2之间有一条长度为5的道路。
- 城市1和城市3之间有一条长度为9的道路。
- 城市2和城市3之间有一条长度为2的道路。
- 城市2和城市4之间有一条长度为6的道路。
- 城市3和城市4之间有一条长度为3的道路。
现在我们以城市1为起点，按照Dijkstra算法的步骤来求解最短路径及其长度。
1. 初始化操作：- 集合S = {1}，dist = [0, ∞, ∞, ∞]，表示起点到各个城市的最短路径长度。
数据结构排序有趣案例
数据结构排序有趣案例一、引言在计算机科学中，排序是一种常见且重要的操作。
通过对数据进行排序，我们可以更高效地搜索、查找和处理数据。
数据结构是排序算法的基础，它们定义了数据的组织方式和操作规则。
本文将介绍一些有趣的案例，展示不同数据结构排序算法的应用和特点。
二、冒泡排序冒泡排序是一种简单但低效的排序算法。
它重复地比较相邻的两个元素，并交换它们的位置，直到整个序列排序完成。
下面是一个用冒泡排序算法对一组整数进行排序的案例：1.原始数据：[5, 3, 8, 4, 2]2.第一次排序：[3, 5, 4, 2, 8]3.第二次排序：[3, 4, 2, 5, 8]4.第三次排序：[3, 2, 4, 5, 8]5.第四次排序：[2, 3, 4, 5, 8]冒泡排序的时间复杂度为O(n^2)，其中n是待排序元素的数量。
虽然冒泡排序效率低下，但它易于理解和实现，适用于小规模数据的排序。
三、选择排序选择排序是一种简单且高效的排序算法。
它将序列分为已排序部分和未排序部分，每次从未排序部分选择最小的元素，并将其放到已排序部分的末尾。
下面是一个用选择排序算法对一组整数进行排序的案例：1.原始数据：[5, 3, 8, 4, 2]2.第一次排序：[2, 3, 8, 4, 5]3.第二次排序：[2, 3, 8, 4, 5]4.第三次排序：[2, 3, 4, 8, 5]5.第四次排序：[2, 3, 4, 5, 8]选择排序的时间复杂度为O(n^2)，与冒泡排序相同。
但选择排序的交换次数较少，因此在某些情况下比冒泡排序更快。
四、插入排序插入排序是一种简单且高效的排序算法。
它将序列分为已排序部分和未排序部分，每次从未排序部分选择一个元素，并插入到已排序部分的正确位置。
下面是一个用插入排序算法对一组整数进行排序的案例：1.原始数据：[5, 3, 8, 4, 2]2.第一次排序：[3, 5, 8, 4, 2]3.第二次排序：[3, 5, 8, 4, 2]4.第三次排序：[3, 4, 5, 8, 2]5.第四次排序：[2, 3, 4, 5, 8]插入排序的时间复杂度为O(n^2)，与冒泡排序和选择排序相同。
常用算法 枚举 排序 查找
常用算法枚举排序查找常用的算法思想包括枚举、排序和查找等多种方法。
具体如下：1. 枚举：这是一种基础的算法思想，通常用于解决问题的所有可能情况数量不多时。
枚举算法会尝试每一种可能性，直到找到问题的解。
这种方法简单直接，但效率不高，尤其是在解空间很大时不太实用。
2. 排序：排序算法用于将一组数据按照特定的顺序进行排列。
常见的排序算法有：-选择排序：一种简单直观的排序算法，工作原理是在未排序序列中找到最小（或最大）的元素，存放到排序序列的起始位置，然后再从剩余未排序元素中继续寻找最小（或最大）元素，放到已排序序列的末尾，如此反复，直至所有元素均排序完毕。
选择排序的时间复杂度为O(n^2)，空间复杂度为O(1)，并且它是一种不稳定的排序方法。
-冒泡排序：通过重复交换相邻逆序的元素来实现排序，时间复杂度同样为O(n^2)，空间复杂度为O(1)，是稳定的排序方法。
-快速排序：采用分治策略来把一个序列分为两个子序列，适用于大数据集合，平均时间复杂度为O(nlogn)。
-归并排序：也是一种分治算法，它将待排序序列分为两个半子序列，分别对其进行排序，最后将有序的子序列合并成整个有序序列，时间复杂度为O(nlogn)，空间复杂度较高。
-堆排序：利用堆这种数据结构所设计的一种排序算法，时间复杂度为O(nlogn)。
3. 查找：查找算法用于在数据集合中寻找特定的数据。
常见的查找算法有：-顺序查找：从数据集的一端开始逐个检查每个元素，直到找到所需的数据或者检查完所有数据。
-二分查找：在有序的数据集中通过不断将查找区间减半来定位数据，时间复杂度为O(logn)。
-哈希查找：通过哈希函数将关键字映射到哈希表中的位置来实现快速查找，理想情况下时间复杂度接近O(1)。
总的来说，这些算法都是计算机科学中的基础内容，它们各自有不同的应用场景和性能特点。
在解决实际问题时，选择合适的算法对于提高效率和程序性能至关重要。
计算机算法面试题及答案
计算机算法面试题及答案1. 问题：请解释什么是时间复杂度，并给出一个例子。
答案：时间复杂度是衡量算法运行时间与输入规模之间关系的量度。
它通常用大O符号表示，例如O(n)、O(n^2)等。
一个例子是冒泡排序算法，其时间复杂度为O(n^2)，因为当数组长度为n时，它需要进行n*(n-1)/2次比较。
2. 问题：描述快速排序算法的过程。
答案：快速排序是一种分治算法，它通过选择一个“基准”元素，将数组分为两部分，一部分包含小于基准的元素，另一部分包含大于基准的元素。
然后递归地对这两部分进行快速排序，直到每个子数组只有一个元素或者为空。
3. 问题：什么是动态规划？请给出一个应用实例。
答案：动态规划是一种通过将复杂问题分解为更小的子问题来解决的方法，并且通过记忆已解决的子问题的结果来避免重复计算。
一个典型的应用实例是斐波那契数列的计算，通过动态规划可以避免大量的重复计算，从而提高效率。
4. 问题：解释图的深度优先搜索（DFS）算法。
答案：深度优先搜索是一种用于遍历或搜索树或图的算法。
它从一个节点开始，尽可能深地搜索树的分支，直到达到一个叶节点，然后回溯到上一个节点，继续搜索下一个分支，直到所有节点都被访问过。
5. 问题：请描述堆排序算法的工作原理。
答案：堆排序是一种基于比较的排序算法，它利用了二叉堆的数据结构。
算法的核心是构建一个最大堆，然后不断移除堆顶元素（最大值），将其放置在数组的末尾，同时调整剩余元素以保持最大堆的性质，直到数组完全排序。
6. 问题：什么是哈希表？它有什么优点？答案：哈希表是一种通过哈希函数将键映射到表中一个位置来访问记录的数据结构。
它的优点包括高效的查找、插入和删除操作，平均时间复杂度为O(1)，这使得哈希表在需要快速访问数据的场景中非常有用。
7. 问题：解释什么是递归算法，并给出一个递归函数的例子。
答案：递归算法是一种自我引用的算法，它通过重复调用自身来解决问题。
一个典型的递归函数例子是计算阶乘的函数，它定义为n! = n * (n-1)!，其中n!是n的阶乘。
排序算法(比较类和非比较类)
0、算法概述0.1 算法分类十种常见排序算法可以分为两大类：∙比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此也称为非线性时间比较类排序。
∙非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此也称为线性时间非比较类排序。
0.2 算法复杂度0.3 相关概念∙稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面。
∙不稳定：如果a原本在b的前面，而a=b，排序之后a 可能会出现在b 的后面。
∙时间复杂度：对排序数据的总的操作次数。
反映当n变化时，操作次数呈现什么规律。
∙空间复杂度：是指算法在计算机内执行时所需存储空间的度量，它也是数据规模n的函数。
1、冒泡排序（Bubble Sort）冒泡排序是一种简单的排序算法。
它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。
走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。
这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。
1.1 算法描述∙比较相邻的元素。
如果第一个比第二个大，就交换它们两个；∙对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；∙针对所有的元素重复以上的步骤，除了最后一个；∙ 重复步骤1~3，直到排序完成。
1.2 代码实现 12 345678 910111213 function bubbleSort(arr) { var len = arr.length; for (var i = 0; i < len - 1; i++) { for (var j = 0; j < len - 1 - i; j++) { if (arr[j] > arr[j+1]) { // 相邻元素两两对比 var temp = arr[j+1]; // 元素交换 arr[j+1] = arr[j]; arr[j] = temp; } } } return arr; }2、选择排序（Selection Sort ）选择排序(Selection-sort)是一种简单直观的排序算法。
堆排序实例演示3
91
16
47
85
36
24
24 36 53 30
85 47 30 53
16
91
如果该序列是一个堆，则对应的这棵完全二叉树的特点是： 所有分支结点的值均不小于 (或不大于)其子女的值，即每棵子 树根结点的值是最大(或最小)的。
堆特点：堆顶元素是整个序列中最大(或最小)的元素。
2022/9/1
数据结构
2
2．堆排序
足堆，继续调 整。
将 堆 顶 元 素 R1 比根小，交换。
与Rn交换)。
2022/9/1
数据结构
d.到了叶子结 点，调整结束， 堆建成。
6
85
30
53
47
53
47
53
47
30
24 36 16 30
24 36 16 85
24 36 16 85
91
91
91
堆调整结束。
R1 与 Rn-1 交 换 ， 堆被破坏。 对 R1 与 Rn-2 调 整。
16
b.调整结束后，以R4为 根的子树满足堆特性。 再将以R3结点为根的 子树调整为堆；
16
c. 以 R3为根的子树满足 堆特性。 再将以R2结点为根的子树 调整为堆；
30
91
91
47
91
47
30
47
85
24 36 53 85 16
24 36 53 85 16
24 36 53 30 16
以 R2 为 根 的 子 树 满 足 堆特性。 再 将 以 R1 结 点 为 根 的 子树调整为堆
d. 调整结束后，整棵树为堆。
建堆过程示例
❖ 例如，图中的完全二叉树表示一个有8个元素的无序序列： {49，38，65，97，76，13，27，49}（相同的两个关 键字49，其中后面一个用49表示），则构造堆的过程如 图3（b）~（f）所示。
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
接着上一Pa说。
就是如何建立这个堆呢。
可以从空的堆开始，然后依次往堆中插入每一个元素，直到所有数都被插入（转移到堆中为止）。
因为插入第i 个元素的所用的时间是O(log i)，所以插入所有元素的整体时间复杂度是O(NlogN)，代码如下。
其实我们还有更快得方法来建立堆。
它是这样的。
直接把99、5、36、7、22、17、46、12、2、19、25、28、1和92这14个数放入一个完全二叉树中（这里我们还是用一个一维数组来存储完全二叉树）。
在这个棵完全二叉树中，我们从最后一个结点开始依次判断以这个结点为根的子树是否符合最小堆的特性。
如果所有的子树都符合最小堆的特性，那么整棵树就是最小堆了。
如果这句话没有理解不要着急，继续往下看。
首先我们从叶结点开始。
因为叶结点没有儿子，所以所有以叶结点为根结点的子树（其实这个子树只有一个结点）都符合最小堆的特性（即父结点的值比子结点的值小）。
这些叶结点压根就没有子节点，当然符合这个特性。
因此所有叶结点都不需要处理，直接跳过。
从第n/2个结点（n为完全二叉树的结点总数，这里即7号结点）开始处理这棵完全二叉树。
注意完全二叉树有一个性质：最后一个非叶结点是第n/2个结点。
以7号结点为根的子树不符合最小堆的特性，因此要向下调整。
同理以6号、5号和4结点为根的子树也不符合最小对的特性，都需要往下调整。
下面是已经对7号、6号、5号和4结点为根结点的子树调整完毕之后的状态。
当然目前这棵树仍然不符合最小堆的特性，我们需要继续调整以3号结点为根的子树，即将3号结点向下调整。
同理继续调整以2号结点为根的子树，最后调整以1号结点为根的子树。
调整完毕之后，整棵树就符合最小堆的特性啦。
小结一下这个创建堆的算法。
把n个元素建立一个堆，首先我可以将这n 个结点以自顶向下、从左到右的方式从1到n编码。
这样就可以把这n个结点转换成为一棵完全二叉树。
紧接着从最后一个非叶结点（结点编号为n/2）开始到根结点（结点编号为1），逐个扫描所有的结点，根据需要将当前结点向下调整，直到以当前结点为根结点的子树符合堆的特性。
虽然讲起来起来很复杂，但是实现起来却很简单，只有两行代码如下：用这种方法来建立一个堆的时间复杂度是O(N)，如果你感兴趣可以尝试自己证明一下，嘿嘿。
堆还有一个作用就是堆排序，与快速排序一样堆排序的时间复杂度也是O(NlogN)。
堆排序的实现很简单，比如我们现在要进行从小到大排序，可以先建立最小堆，然后每次删除顶部元素并将顶部元素输出或者放入一个新的数组中，直到堆为空为止。
最终输出的或者存放在新数组中数就已经是排序好的了。
建堆以及堆排序的完整代码如下：1 2 3 4 5 6 7 8 9101112131415161718 #include <stdio.h>int h[ 101];//用来存放堆的数组int n;//用来存储堆中元素的个数，也就是堆的大小//交换函数，用来交换堆中的两个元素的值void swap(int x,int y){int t;t=h[ x];h[ x]=h[ y];h[ y]=t;}//向下调整函数void siftdown(int i) //传入一个需要向下调整的结点编号i，这里传入1，即从堆的顶点开始向下调整1920212223242526272829303132333435363738394041424344454647 {int t,flag=0;//flag用来标记是否需要继续向下调整//当i结点有儿子的时候（其实是至少有左儿子的情况下）并且有需要继续调整的时候循环窒执行while( i*2<=n && flag==0 ){//首先判断他和他左儿子的关系，并用t记录值较小的结点编号if( h[ i] > h[ i*2] )t=i*2;elset=i;//如果他有右儿子的情况下，再对右儿子进行讨论if(i*2+1 <= n){//如果右儿子的值更小，更新较小的结点编号if(h[ t] > h[ i*2+1])t=i*2+1;}//如果发现最小的结点编号不是自己，说明子结点中有比父结点更小的if(t!=i){4849505152535455565758596061626364656667686970717273747576swap(t,i);//交换它们，注意swap函数需要自己来写i=t;//更新i为刚才与它交换的儿子结点的编号，便于接下来继续向下调整}elseflag=1;//则否说明当前的父结点已经比两个子结点都要小了，不需要在进行调整了}}//建立堆的函数void creat(){int i;//从最后一个非叶结点到第1个结点依次进行向上调整for(i=n/2;i>=1;i--){siftdown(i);}}//删除最大的元素int deletemax(){7778798081828384858687int t;t=h[ 1];//用一个临时变量记录堆顶点的值h[ 1]=h[ n];//将堆得最后一个点赋值到堆顶n--;//堆的元素减少1siftdown(1);//向下调整return t;//返回之前记录的堆得顶点的最大值}int main(){int i,num;//读入数的个数scanf("%d",&num);for(i=1;i<=num;i++)scanf("%d",&h[ i]);n=num;//建堆creat();//删除顶部元素，连续删除n次，其实夜就是从大到小把数输出来可以输入以下数据进行验证1499 5 36 7 22 17 46 12 2 19 25 28 1 92运行结果是1 2 5 7 12 17 19 22 25 28 36 46 92 99当然堆排序还有一种更好的方法。
从小到大排序的时候不建立最小堆而建立最大堆。
最大堆建立好后，最大的元素在h[ 1]。
因为我们的需求是从小到大排序，希望最大的放在最后。
因此我们将h[ 1]和h[ n]交换，此时h[ n]就是数组中的最大的元素。
请注意，交换后还需将h[ 1]向下调整以保持堆的特性。
OK现在最大的元素已经归位，需要将堆的大小减1即n--，然后再将h[ 1]和h[ n]交换，并将h[ 1]向下调整。
如此反复，直到堆的大小变成1为止。
此时数组h中的数就已经是排序好的了。
代码如下：完整的堆排序的代码如下，注意使用这种方法来进行从小到大排序需要建立最大堆。
1617181920212223242526272829303132333435363738394041424344 //向下调整函数void siftdown(int i) //传入一个需要向下调整的结点编号i，这里传入1，即从堆的顶点开始向下调整{int t,flag=0;//flag用来标记是否需要继续向下调整//当i结点有儿子的时候（其实是至少有左儿子的情况下）并且有需要继续调整的时候循环窒执行while( i*2<=n && flag==0 ){//首先判断他和他左儿子的关系，并用t记录值较大的结点编号if( h[ i] < h[ i*2] )t=i*2;elset=i;//如果他有右儿子的情况下，再对右儿子进行讨论if(i*2+1 <= n){//如果右儿子的值更大，更新较小的结点编号if(h[ t] < h[ i*2+1])t=i*2+1;}4546474849505152535455565758596061626364656667686970717273//如果发现最大的结点编号不是自己，说明子结点中有比父结点更大的if(t!=i){swap(t,i);//交换它们，注意swap函数需要自己来写i=t;//更新i为刚才与它交换的儿子结点的编号，便于接下来继续向下调整}elseflag=1;//则否说明当前的父结点已经比两个子结点都要大了，不需要在进行调整了}}//建立堆的函数void creat(){int i;//从最后一个非叶结点到第1个结点依次进行向上调整for(i=n/2;i>=1;i--){siftdown(i);}}74757677787980818283848586878889 //堆排序void heapsort(){while(n>1){swap(1,n);n--;siftdown(1);}}int main(){int i,num;//读入n个数scanf("%d",&num);for(i=1;i<=num;i++)scanf("%d",&h[ i]);n=num;//建堆creat();可以输入以下数据进行验证1499 5 36 7 22 17 46 12 2 19 25 28 1 92运行结果是1 2 5 7 12 17 19 22 25 28 36 46 92 99OK，最后还是要总结一下。
像这样支持插入元素和寻找最大（小）值元素的数据结构称之为优先队列。
如果使用普通队列来实现这个两个功能，那么寻找最大元素需要枚举整个队列，这样的时间复杂度比较高。
如果已排序好的数组，那么插入一个元素则需要移动很多元素，时间复杂度依旧很高。
而堆就是一种优先队列的实现，可以很好的解决这两种操作。
另外Dijkstra算法中每次找离源点最近的一个顶点也可以用堆来优化，使算法的时间复杂度降到O((M+N)logN)。
堆还经常被用来求一个数列中第K大的数。
只需要建立一个大小为K的最小堆，堆顶就是第K大的数。
如果求一个数列中第K小的数，只最需要建立一个大小为K的最大堆，堆顶就是第K小的数，这种方法的时间复杂度是O(NlogK)。
当然你也可以用堆来求前K大的数和前K小的数。
你还能想出更快的算法吗？有兴趣的同学可以去阅读《编程之美》第二章第五节。
堆排序算法是由J.W.J. Williams在1964年发明，他同时描述了如何使用堆来实现一个优先队列。
同年，由Robert W．Floyd提出了建立堆的线性时间算法。