当前位置：网站首页>堆排序

堆排序

2022-07-15 11:07:00 【51CTO】

堆

堆的介绍

首先，堆的前提：完全二叉树，添加时就是从最下面最左。
堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。如下图：

堆排序_#include

同时，我们对堆中的结点按层进行编号，将这种逻辑结构映射到数组中就是下面这个样子

堆排序_堆排序_02

该数组从逻辑上讲就是一个堆结构，我们用简单的公式来描述一下堆的定义就是：

大顶堆：arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]

小顶堆：arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]

ok，了解了这些定义。接下来，我们来看看堆排序的基本思想及基本步骤：

堆排序基本思想：堆排序的基本思想是：将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了
步骤一构造初始堆。将给定无序序列构造成一个大顶堆（一般升序采用大顶堆，降序采用小顶堆)。

a.假设给定无序序列结构如下

堆排序_堆排序_03

2.此时我们从最后一个非叶子结点开始（叶结点自然不用调整，第一个非叶子结点 arr.length/2-1=5/2-1=1，也就是下面的6结点），从左至右，从下至上进行调整。

堆排序_结点_04

4.找到第二个非叶节点4，由于[4,9,8]中9元素最大，4和9交换。

堆排序_堆排序_05

这时，交换导致了子根[4,5,6]结构混乱，继续调整，[4,5,6]中6最大，交换4和6。

堆排序_结点_06

此时，我们就将一个无需序列构造成了一个大顶堆。

**步骤二将堆顶元素与末尾元素进行交换，使末尾元素最大。然后继续调整堆，再将堆顶元素与末尾元素交换，得到第二大元素。如此反复进行交换、重建、交换。

a.将堆顶元素9和末尾元素4进行交换

堆排序_结点_07

b.重新调整结构，使其继续满足堆定义

堆排序_#include_08

c.再将堆顶元素8与末尾元素5进行交换，得到第二大元素8.

堆排序_#include_09

后续过程，继续进行调整，交换，如此反复进行，最终使得整个序列有序

堆排序_结点_10

再简单总结下堆排序的基本思路：

a.将无需序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆;
　　b.将堆顶元素与末尾元素交换，将最大元素"沉"到数组末端;
　　c.重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序。

上面来自orz 感谢我对堆排序的理解：

如果让你构建一个堆的话，首先你可以用数组给他存下来，当然这是又可以让数组下标为0，或者1 为堆顶，我习惯用1，
**你选择一个结点是i，则他父亲结点是i/2; 他的左叶子结点是 2i; 右叶子结点是2i+1；**如果是从零开始：他的父亲节点是（i-1）/2；左叶子结点 2i+1; 右叶子结点：2i+2;
如果是大顶堆的话就是把大的放数组前面，也就是把大的放在父亲节点，找出最大的之后，把最大的与堆尾元素换一下，也就把最大的存放到数组最后一位了，然后进行剩下的比较，同样操作拿出最大的放在堆尾…这样就得到一个递增的数列。
如果是武学构建堆的话，就从最后一个叶子结点的父亲结点（c）处开始，之后再找结点（c-1）；一直找到堆顶。

有一个小栗子可以看一下帮助理解吧；

问题 C: Leopard学霸
来自UPC。
题目描述
马上假期就要到了，THU的神犇Leopard假期里都不忘学霸，现在有好多门功课，每门功课都耗费他1单位时间来学习。他的假期从0时刻开始，有1000000000个单位时间（囧rz）。在任意时刻，他都可以任意一门功课（编号1~n）来学习。因为他在每个单位时间只能学习一门功课，而每门功课又都有一个截止日期，所以他很难完成所有n门功课。对于第i门功课，有一个截止时间Di，若他能学完这门功课，他能够获得知识Pi。在给定的功课和截止时间下，Leopard能够获得的知识最多为多少呢？
输入
第一行，一个整数n，表示功课的数目接下来n行，每行两个整数，Di和Pi
输出
输出一行一个整数，表示最多学得的知识数
样例输入 Copy
3
2 10
1 5
1 7
样例输出 Copy
17
提示
样例说明：第一个单位时间学习第3个功课（1，7），然后在第二个单位时间学习第1个功课(2，10）
【数据范围】
10%数据满足：n<=25
60%数据满足：n<10000
100%数据满足：1<=n<=100000,Di、Pi<=1000000000 最后的答案可能超过32位整型。
思路就是；堆排列，就是先是需要瞒住时间要求，在满足时间条件的前提下，比较大小，小的减下去，把大的加上。也就是一个不断在更新的过程。

       
       #include 
       
       <
       
       cstdio
       
       >
       
       #include 
       
       <
       
       cstring
       
       >
       
       #include 
       
       <
       
       algorithm
       
       >
       
       #include 
       
       <
       
       map
       
       >
       
       #include 
       
       <
       
       queue
       
       >
       
       #include 
       
       <
       
       string
       
       >
       
       #include
       
       <
       
       iostream
       
       >
       
       #include
       
       <
       
       stdio.
       
       h
       
       >
       
       #include
       
       <
       
       string.
       
       h
       
       >
       
       #include 
       
       <
       
       algorithm
       
       >
       
       typedef 
       
       long 
       
       long 
       
       ll;
       
       using 
       
       namespace 
       
       std;
       
       const 
       
       int 
       
       maxn
       
       =
       
       2e6
       
       +
       
       1010;
       
       #define
       
       const 
       
       int 
       
       mod
       
       =
       
       998244353;
       
       map
       
       <
       
       string,
       
       ll
       
       > 
       
       mp;
       
       priority_queue
       
       <
       
       ll
       
       > 
       
       qq;
       
       ll 
       
       f[
       
       maxn],
       
       a[
       
       maxn],
       
       b[
       
       maxn],
       
       n,
       
       m,
       
       p,
       
       flag,
       
       temp,
       
       sum;
       
       char 
       
       str[
       
       10][
       
       10];
       
       struct 
       
       node{
       
       int 
       
       a,
       
       b;
       
}
       
       q[
       
       maxn];
       
       bool 
       
       cmp(
       
       node 
       
       a,
       
       node 
       
       b){
       
       return 
       
       a.
       
       a
       
       <
       
       b.
       
       a;
       
}
       
       void 
       
       up(
       
       int 
       
       now){
       
       //保证堆首一定是最小的 就是可以用后面的替换 
       
       while(
       
       now 
       
       > 
       
       1 
       
       && 
       
       a[
       
       now] 
       
       < 
       
       a[
       
       now
       
       /
       
       2]){
       
       //把最小的换到堆首
       
       swap(
       
       a[
       
       now],
       
       a[
       
       now
       
       /
       
       2]);
       
       up( 
       
       now 
       
       / 
       
       2);
       
  }
       
}
       
       void 
       
       down(
       
       int 
       
       now){
       
       while(
       
       a[
       
       now
       
       *
       
       2]
       
       <
       
       a[
       
       now]
       
       ||
       
       a[
       
       now
       
       *
       
       2
       
       +
       
       1]
       
       <
       
       a[
       
       now]){
       
       //比较左右子树 
       
       int 
       
       w
       
       =
       
       now
       
       *
       
       2;
       
       //先比较左右子树谁更小，因为根节点要最小的 
       
       if(
       
       a[
       
       now
       
       *
       
       2
       
       +
       
       1]
       
       <
       
       a[
       
       now
       
       *
       
       2])
       
       w
       
       ++;
       
       swap(
       
       a[
       
       w],
       
       a[
       
       now]);
       
       down(
       
       w);
       
       //继续下面子树的比较 
       
  }
       
}
       
       int 
       
       main (){
       
       cin
       
       >>
       
       n;
       
       for(
       
       int 
       
       i 
       
       = 
       
       1; 
       
       i 
       
       <= 
       
       n; 
       
       i
       
       ++)
       
  {
       
       scanf(
       
       "%lld%lld",
       
       &
       
       q[
       
       i].
       
       a,
       
       &
       
       q[
       
       i].
       
       b);
       
  }
       
       sort( 
       
       q
       
       +
       
       1, 
       
       q
       
       +
       
       1
       
       +
       
       n, 
       
       cmp);
       
       memset( 
       
       a, 
       
       inf, 
       
       sizeof(
       
       a));
       
       for(
       
       int 
       
       i
       
       =
       
       1;
       
       i
       
       <=
       
       n;
       
       i
       
       ++)
       
  {
       
       if(
       
       m
       
       +
       
       1
       
       <=
       
       q[
       
       i].
       
       a){
       
       //可行 
       
       sum
       
       +=
       
       q[
       
       i].
       
       b;
       
       m
       
       ++;
       
       a[
       
       ++
       
       p]
       
       =
       
       q[
       
       i].
       
       b;
       
       up(
       
       p);
       
       //就是把这个数存放里面之后需要排序
       
    }
       
       else 
       
       if(
       
       a[
       
       1]
       
       <
       
       q[
       
       i].
       
       b){
       
       //满足 堆顶元素比这个元素小就是用这个元素替换掉堆顶元素 
       
       sum
       
       =
       
       sum
       
       -
       
       a[
       
       1]
       
       +
       
       q[
       
       i].
       
       b;
       
       a[
       
       1]
       
       =
       
       q[
       
       i].
       
       b;
       
       down(
       
       1);
       
       //既然换掉了所以排序被打乱，就需要在排 ，这个就得从上往下排了，因为这个堆顶变了。
       
    }
       
  }
       
       cout
       
       <<
       
       sum
       
       <<
       
       endl;
       
       return 
       
       0;
       
}
      
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.

补充

最近学会用优先队列来写堆了，上面的，堆排序其实就是把他从大到小，或者从小到大，

       
       priority_queue
       
       <
       
       ll , 
       
       vector
       
       <
       
       ll
       
       > , 
       
       greater
       
       <
       
       ll
       
       > 
       
       > 
       
       mn;
       
       //上 小根堆 小到大 
       
       priority_queue
       
       <
       
       ll , 
       
       vector
       
       <
       
       ll
       
       > , 
       
       less
       
       <
       
       ll
       
       > 
       
       > 
       
       mx;
       
       //下 大根堆 大到小
      
1.
2.