数据结构-堆排序

文章目录

• 1、向下调整
• 2、向上调整
• 3、建立堆
• 4、堆排序
• 5、删除堆首
• 6、增加元素
• 7、完成代码

堆是由一维数组存储的完全二叉树，下标从1开始，因此下标最大的非叶子节点为n/2（可以动手画画想想）。

本篇文章以建立大根堆为例。

1、向下调整

使用向下调整方式建立堆时，直接选择非叶子节点。

void down(int low, int high){
 
	int i = low;
	int j = i*2;
	
	while(j<= high){
		//如果含有右孩子，并且右孩子大于左孩子则将j置为右孩子
		if(j+1 <= high && heap[j+1] > heap[j])j = j+1;
		 
		//如果孩子中的最大值大于自身，交换
		if(heap[j] > heap[i]){
			swap(heap[i],heap[j]);
			//继续向下调整
			i = j;
			j=i*2;
		}else{
			break;
		}
	}
}

2、向上调整

向上调整思路简单，有没有父亲节点，自身是否大于父亲节点。

void up(int low,int high){
 
	int i = high;
	int j = i/2;
	
	while(j >= low){
		if(heap[i] > heap[j]){
			swap(heap[j],heap[i]);
			i = j;
			j = i/2;
		}else{
			break;
		}
	}
	
}

3、建立堆

void creatheap(){
	for(int i = n/2; i >= 1;i--){
		
		down(i,n);
	}
}

4、堆排序

堆排序非常简单，明白了如何建成大根堆，每次把顶点（最大值）放到最尾端就不要再动了，最尾端向前移动一个位置，然后再建立大根堆，再将最大值放到最尾端。

直接看代码更清晰。

void heapsort(){
	for(int i = n; i > 1; i--){
		swap(heap[1],heap[i]);
		down(1,i-1);
	}
}
//是不是soeasy

5、删除堆首

void deleteTop(){
	heap[1] = heap[n--];
	down(1,n);
}

6、增加元素

void insert(int x){
	heap[++n]=x;
	//插入元素堆要重新调整 
	creatheap();
}

总之，无论使用什么的 *** 作吧，插入，删除都好，你心里面要清楚，你的 *** 作是否导致你的堆还是大根堆或者时小根堆，明白这一点再进行下一步的 *** 作。

7、完成代码

输入

5
2 8 5 1 3

输出

1 2 3 5 8

#include
#include
#include
 
using namespace std;
const int MAXN = 1005;
int heap[MAXN];
int n;
void up(int low,int high){
 
	int i = high;
	int j = i/2;
	
	while(j >= low){
		if(heap[i] > heap[j]){
 
			swap(heap[j],heap[i]);
			i = j;
			j = i/2;
		}else{
			break;
		}
	}
	
}
void down(int low, int high){
 
	int i = low;
	int j = i*2;
	
	while(j<= high){
		if(j+1 <= high && heap[j+1] > heap[j])j = j+1;
		if(heap[j] > heap[i]){
			swap(heap[i],heap[j]);
			i = j;
			j=i*2;
		}else{
			break;
		}
	}
}


void creatheap(){
	for(int i = n/2; i >= 1;i--){
		down(i,n);
	}
}

void heapsort(){
	for(int i = n; i > 1; i--){
		swap(heap[1],heap[i]);
		down(1,i-1);
	}
}

void deleteTop(){
	heap[1] = heap[n--];
	down(1,n);
}

void insert(int x){
	heap[++n]=x;
	//插入元素堆要重新调整 
	creatheap();
}

void print(){
	for(int i = 1; i <=n; i++){
		cout << heap[i] << " ";
	}
}
int main(){
	 
	 cin >> n;
	 
	 for(int i = 1; i <= n; i++){
	 	cin >> heap[i];
	 }
	 
	//堆中从n/2个节点开始为非叶子节点 
	creatheap();
	heapsort(); 
	insert(4);
 	heapsort();
 	print();
	return 0;
}