06 堆排序

#数据结构 #堆

6.1 堆

  1. 堆的定义：
    1. 是一棵完全二叉树
    2. 每个节点的值都大于或等于其子节点的值，为最大堆；反之为最小堆。
  2. 堆的存储：一般用数组来表示堆，下标为i的结点的父结点下标为；其左右子结点分别为 、（若数组编号从0开始）。下标为i的结点的父结点下标为；其左右子结点分别为、（若数组编号从1开始）

6.2 维护堆的性质

  1. 递归维护 
     // 维护最大堆的性质  
 // arr:一个最大堆的数组  
 // i:需要调整的堆中的元素  
 void max_heapify(int arr[], int i, int n){  
     // 从a[i] a[l] a[r]选择最大的  
     int l = 2*i+1, r = 2*i+2;  
     int largest = i;  
     if(l <= n && arr[l]>arr[i]){  
         largest = l;  
     }  
     if(r <= n && arr[r]>arr[largest]){  
         largest = r;  
     }  
     // 如果a[i]最大，程序结束  
     if(largest != i){  
         swap(&arr[i], &arr[largest]);  
         max_heapify(arr, largest);  
     }  
 }  
 ​  
 void swap(int* a, int* b) {  
     int temp = *b;  
     *b = *a;  
     *a = temp;  
 }
 ```
  2. 非递归维护 
     // 维护最大堆的性质  
 // arr:一个最大堆的数组  
 // i:需要调整的堆中的元素  
 void max_heapify(int arr[], int start, int end) {  
     //建立父节点指标和子节点指标  
     int dad = start;  
     int son = dad * 2 + 1;  
     while (son <= end) { //若子节点指标在范围内才做比较  
         if (son + 1 <= end && arr[son] < arr[son + 1]) //先比较两个子节点大小，选择最大的  
             son++;  
         if (arr[dad] > arr[son]) //如果父节点大于子节点代表调整完毕，直接跳出函数  
             return;  
         else { //否则交换父子内容再继续子节点和孙节点比较  
             swap(&arr[dad], &arr[son]);  
             dad = son;  
             son = dad * 2 + 1;  
         }  
     }  
 }  
 ​  
 void swap(int* a, int* b) {  
     int temp = *b;  
     *b = *a;  
     *a = temp;  
 }
    时间复杂度或对于树高h的节点来说，时间复杂度

6.3 建堆

 void build_max_heap(int arr[ ],int n){  
     int i;  
     int temp;  
     for(i=n/2-1; i>=0; i--) // 建初始堆积  
         max_heapify(arr, i, n);  
 }

时间复杂度

6.4 堆排序算法

  1. 排序步骤

    1. 建堆（得到最大堆）。
    2. 将堆的第一个元素与堆积的最后那个元素交换位置。(即“去掉”最大值元素）
    3. 维护最大堆（将“去掉”最大值元素后剩下的元素组成的子序列重新转换一个新的堆）。
    4. 重复上述过程的第2至第3步n-1次。

  2. 非递归维护最大堆

     // 堆排序  
 int* heapsort(int arr[], int n){  
     build-max-heap(arr, n);  
     for(int i=n-1; i>=1; i--){  
         swap(&arr[0], &arr[i]);  
         n--;  
         max-heapify(arr, 0, n)  
     }  
 }  
 ​  
 // 建堆  
 void build_max_heap(int arr[ ],int n){  
     int i;  
     int temp;  
     for(i=n/2-1; i>=0; i--) // 建初始堆积  
         max_heapify(arr, i, n);  
 }  
 ​  
 // 维护最大堆的性质  
 // arr:一个最大堆的数组  
 // i:需要调整的堆中的元素  
 void max_heapify(int arr[], int i, int n){  
     // 从a[i] a[l] a[r]选择最大的  
     int l = 2*i+1, r = 2*i+2;  
     int largest = i;  
     if(l <= n && arr[l]>arr[i]){  
         largest = l;  
     }  
     if(r <= n && arr[r]>arr[largest]){  
         largest = r;  
     }  
     // 如果a[i]最大，程序结束  
     if(largest != i){  
         swap(&arr[i], &arr[largest]);  
         max_heapify(arr, largest);  
     }  
 }  
 ​  
 void swap(int* a, int* b) {  
     int temp = *b;  
     *b = *a;  
     *a = temp;  
 }
 ```

  3. 递归维护最大堆

     #include <stdio.h>  
 #include <stdlib.h>  
 void swap(int* a, int* b) {  
     int temp = *b;  
     *b = *a;  
     *a = temp;  
 }  
 ​  
 // 维护最大堆的性质  
 // arr:一个最大堆的数组  
 // i:需要调整的堆中的元素  
 void max_heapify(int arr[], int start, int end) {  
     //建立父节点指标和子节点指标  
     int dad = start;  
     int son = dad * 2 + 1;  
     while (son <= end) { //若子节点指标在范围内才做比较  
         if (son + 1 <= end && arr[son] < arr[son + 1]) //先比较两个子节点大小，选择最大的  
             son++;  
         if (arr[dad] > arr[son]) //如果父节点大于子节点代表调整完毕，直接跳出函数  
             return;  
         else { //否则交换父子内容再继续子节点和孙节点比较  
             swap(&arr[dad], &arr[son]);  
             dad = son;  
             son = dad * 2 + 1;  
         }  
     }  
 }  
 // 堆排序算法  
 void heap_sort(int arr[], int len) {  
     int i;  
     //建堆，初始化，i从最后一个父节点开始调整  
     for (i = len / 2 - 1; i >= 0; i--)  
         max_heapify(arr, i, len - 1);  
     //先将第一个元素和已排好元素前一位做交换，再从新调整，直到排序完毕  
     for (i = len - 1; i > 0; i--) {  
         swap(&arr[0], &arr[i]);  
         max_heapify(arr, 0, i - 1);  
     }  
 }  
 int main() {  
     int arr[] = { 3, 5, 3, 0, 8, 6, 1, 5, 8, 6, 2, 4, 9, 4, 7, 0, 1, 8, 9, 7, 3, 1, 2, 5, 9, 7, 4, 0, 2, 6 };  
     int len = (int) sizeof(arr) / sizeof(*arr);  
     heap_sort(arr, len);  
     int i;  
     for (i = 0; i < len; i++)  
         printf("%d ", arr[i]);  
     printf("\n");  
     return 0;  
 }

     #include <iostream>  
 #include <algorithm>  
 using namespace std;  
 void max_heapify(int arr[], int start, int end) {  
     //建立父节点指标和子节点指标  
     int dad = start;  
     int son = dad * 2 + 1;  
     while (son <= end) { //若子节点指标在范围内才做比较  
         if (son + 1 <= end && arr[son] < arr[son + 1]) //先比较两个子节点大小，选择最大的  
             son++;  
         if (arr[dad] > arr[son]) //如果父节点大于子节点代表调整完毕，直接跳出函数  
             return;  
         else { //否则交换父子内容再继续子节点和孙节点比较  
             swap(arr[dad], arr[son]);  
             dad = son;  
             son = dad * 2 + 1;  
         }  
     }  
 }  
 void heap_sort(int arr[], int len) {  
     //初始化，i从最后一个父节点开始调整  
     for (int i = len / 2 - 1; i >= 0; i--)  
         max_heapify(arr, i, len - 1);  
     //先将第一个元素和已经排好的元素前一位做交换，再从新调整(刚调整的元素之前的元素)，直到排序完毕  
     for (int i = len - 1; i > 0; i--) {  
         swap(arr[0], arr[i]);  
         max_heapify(arr, 0, i - 1);  
     }  
 }  
 int main() {  
     int arr[] = { 3, 5, 3, 0, 8, 6, 1, 5, 8, 6, 2, 4, 9, 4, 7, 0, 1, 8, 9, 7, 3, 1, 2, 5, 9, 7, 4, 0, 2, 6 };  
     int len = (int) sizeof(arr) / sizeof(*arr);  
     heap_sort(arr, len);  
     for (int i = 0; i < len; i++)  
         cout << arr[i] << ' ';  
     cout << endl;  
     return 0;  
 }

时间复杂度

6.5 优先队列

6.5.1 my优先队列(c)

  1. 读最大元素 O(1)
int heap-maximum(int arr[]){  
	 return arr[0];  
}

 
  1. c移走最大元素 O(lgn)
	  int heap-extract-max(int arr[], int n){  
	 if(n < 1){  
		 printf("HEAP UNDERFLOW");  
	 }  
	 int max = arr[0];  
	 arr[0] = arr[n-1];  
	 n--;  
	 max_heapify(arr, 0, n);  
	 return max;  
}
  1. c增加某结点的值 O(lgn)
void heap-increase-key(int arr[], int i, int key){  
	 if(key < arr[i]){  
		 printf("NEW KEY IS SMALLER THAN CURRENT KEY");  
	 }  
	 arr[i] = key;  
	 while(i>0 && arr[(i-1)/2]<arr[i]){  
		 swap(&a[i], &arr[(i-1)/2]);  
		 i = (i-1)/2;  
	 }  
}
  1. 插入一个新节点 O(lgn)
void max-heap-insert(int arr[], int key, int n){  
	 n++;  
	 a[n-1] = key-1;  
	 heap-increase-key(arr, n-1, key);  
}

6.5.2 cpp的自带优先队列

6.5.2.1 优先队列的声明

基本格式：priority_queue<结构类型> 队列名
常用格式：

 priority_queue <int> i;  
 priority_queue <double> d;  
 ​  
 priority_queue <node> q;  
 //node是一个结构体  
 //结构体里重载了‘<’小于符号  
 ​  
 priority_queue <int,vector<int>,greater<int> > q;  
 //不需要#include<vector>头文件  
 //注意后面两个“>”不要写在一起，“>>”是右移运算符  
 ​  
 priority_queue <int,vector<int>,less<int> >q;

6.5.2.2 默认的优先队列

 #include<cstdio>  
 #include<queue>  
 using namespace std;  
 priority_queue <int> q;  
 int main()  
 {  
     q.push(10),q.push(8),q.push(12),q.push(14),q.push(6);  
     while(!q.empty())  
         printf("%d ",q.top()),q.pop();  
 }  
 ​  
 // 【输出】14 12 10 8 6

6.5.2.3 默认的优先队列（结构体，重载小于）

重载运算符的格式

 bool operator<(const struct_name& other) const {  
     // 你的比较逻辑  
 }

重载小于号的格式

 struct point{  
     int x,y;  
     bool operator < (const point &a) const{  
         return x>a.x||x==a.x&&x>a.y;  
     }  
 }a[5];

 #include<cstdio>  
 #include<queue>  
 using namespace std;  
 struct node  
 {  
     int x,y;  
     bool operator < (const node & a) const  // 重载小于，x更小的结构体更小  
     {  
         return x<a.x;  
     }  
 }k;  
 priority_queue <node> q;  
 int main()  
 {  
     k.x=10,k.y=100; q.push(k);  
     k.x=12,k.y=60; q.push(k);  
     k.x=14,k.y=40; q.push(k);  
     k.x=6,k.y=80; q.push(k);  
     k.x=8,k.y=20; q.push(k);  
     while(!q.empty())  
     {  
         node m=q.top(); q.pop();  
         printf("(%d,%d) ",m.x,m.y);  
     }  
 }  
 ​  
 // 【输出】(14,40) (12,60) (10,100) (8,20) (6,80)

6.5.2.4 less和greater优先队列

 ```cpp
#include
#include
using namespace std;
priority_queue <int,vector,less > p;
priority_queue <int,vector,greater > q;
int a[5]={10,12,14,6,8};
int main()
{
for(int i=0;i<5;i++)
p.push(a[i]),q.push(a[i]);

 
printf("less:")；
while(!p.empty())
printf("%d ",p.top()),p.pop();

 
printf("\ngreater:")；
while(!q.empty())
printf("%d ",q.top()),q.pop();
}
​
// 【结果】
// less:14 12 10 8 6
// greater:6 8 10 12 14


#### 结构体优先队列的另一种排序方法

```cpp
 #include<queue>  
 #include<cstdio>  
 #include<cstring>  
 #include<iostream>  
 #include<algorithm>  
 using namespace std;  
 ​  
 int n;  
 struct node{  
     int fir,sec;  
     void Read() {scanf("%d %d",&fir,&sec);}  
 }input;  
 ​  
 struct cmp1{  
     bool operator () (const node &x,const node &y) const{  
         return x.fir<y.fir;  
     }  
 };//当一个node x的fir值小于另一个node y的fir值时，称x<y  
 ​  
 struct cmp2{  
     bool operator () (const node &x,const node &y) const{  
         return x.sec<y.sec;    
     }  
 };//当一个node x的sec值小于另一个node y的sec值时，称x<y  
 ​  
 struct cmp3{  
     bool operator () (const node &x,const node &y) const{  
         return x.fir+x.sec<y.fir+y.sec;   
     }  
 };//当一个node x的fri值和sec值的和小于另一个node y的fir值和sec值的和时，称x<y  
 ​  
 priority_queue<node,vector<node>,cmp1> q1;  
 priority_queue<node,vector<node>,cmp2> q2;  
 priority_queue<node,vector<node>,cmp3> q3;  
 ​  
 int main()  
 {  
     scanf("%d",&n);  
     for(int i=1;i<=n;i++) input.Read(),q1.push(input),q2.push(input),q3.push(input);  
       
     printf("\ncmp1:\n");  
     while(!q1.empty()) printf("(%d,%d) ",q1.top().fir,q1.top().sec),q1.pop();     
           
     printf("\n\ncmp2:\n");  
     while(!q2.empty()) printf("(%d,%d) ",q2.top().fir,q2.top().sec),q2.pop();     
           
     printf("\n\ncmp3:\n");  
     while(!q3.empty()) printf("(%d,%d) ",q3.top().fir,q3.top().sec),q3.pop();     
 }

【输入】

 7  
 1 2  
 2 1  
 6 9  
 9 6  
 -100 100  
 -500 20  
 4000 -3000

【输出】

 cmp1:  
 (4000,-3000) (9,6) (6,9) (2,1) (1,2) (-100,100) (-500,20)  
 ​  
 cmp2:  
 (-100,100) (-500,20) (6,9) (9,6) (1,2) (2,1) (4000,-3000)  
 ​  
 cmp3:  
 (4000,-3000) (6,9) (9,6) (1,2) (2,1) (-100,100) (-500,20)
Built with MDFriday ❤️