堆排序
- 堆的定义：
- 是一棵完全二叉树
- 每个节点的值都大于或等于其子节点的值，为最大堆；反之为最小堆。
- 堆的存储：一般用数组来表示堆，下标为 i 的结点的父结点下标为(i-1)/2；其左右子结点分别为 (2i + 1)、(2i + 2)
- 排序步骤
- 将原始序列转换为第一个堆。
- 将堆的第一个元素与堆积的最后那个元素交换位置。(即“去掉”最大值元素）
- 将“去掉”最大值元素后剩下的元素组成的子序列重新转换一个新的堆。
- 重复上述过程的第2至第3步n-1次。
/* 调整子算法
功能：向下调整结点i的位置，使得其祖先结点值都比其大。如果一棵树仅根结点i不满足堆条件，通过该函数可将其调整为一个堆。
K :序列
i :被调整的二叉树的根的序号
n :被调整的二叉树的结点数目
*/
void adjust(keytype k[ ], int i, int n){
int j;
keytype temp;
temp = k[i];
j = 2*i+1;
while(j < n){
if(j+1<n && k[j]<k[j+1])
j++;
if(temp < k[j]) {
k[(j-1)/2] = k[j];
j = 2*j+1;
}else
break;
}
k[(j-1)/2] = temp;
}
// 堆排序算法
void heapSort(keytype k[ ],int n){
int i;
keytype temp;
for(i=n/2-1; i>=0; i--) // 建初始堆积
adjust(k, i, n);
for(i=n-1; i>=1; i--){ // 具体排序
temp = k[i];
k[i] = k[0];
k[0] = temp;
adjust(k, 0, i);
}
}
#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;
}
优先队列
优先队列的声明
基本格式：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;
默认的优先队列
#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
默认的优先队列（结构体，重载小于）
重载运算符的格式
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)
less和greater优先队列
#include<cstdio>
#include<queue>
using namespace std;
priority_queue <int,vector<int>,less<int> > p;
priority_queue <int,vector<int>,greater<int> > 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<int>:")；
while(!p.empty())
printf("%d ",p.top()),p.pop();
printf("\ngreater<int>:")；
while(!q.empty())
printf("%d ",q.top()),q.pop();
}
// 【结果】
// less<int>:14 12 10 8 6
// greater<int>:6 8 10 12 14
结构体优先队列的另一种排序方法
#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)
