堆排序

最新推荐文章于 2021-07-24 23:27:25 发布

wenjiashun

最新推荐文章于 2021-07-24 23:27:25 发布

阅读量406

点赞数

分类专栏：数据结构与算法（C++实现）文章标签： struct 二叉树堆排序

本文链接：https://blog.csdn.net/wenjiashun/article/details/38894277

版权

数据结构与算法（C++实现）专栏收录该内容

10 篇文章

订阅专栏

//heapSort.cpp

#include <iostream>
#include <ctime>
#include <cstdlib>
#define NUMBER 9
using namespace std;

struct heapType
{
	int heapArray[NUMBER+1];//数组中存放20个元素，从1到20；
	int arraySize;//数组长度
	int heapSize;//建的堆中元素个数
};

void maxHeapify(heapType &h,int i);//i处保证其满足最大堆的性质
void exchange(int *x,int *y);
void buildMaxHeap(heapType &h);//建堆操作
void heapSort(heapType &h);//堆排序操作
void print(heapType &h);

int main()
{
	heapType heap;
	heap.arraySize = NUMBER;
	heap.heapArray[0] = 0;
	srand(unsigned(time(NULL)));
	for(int i=1;i<=heap.arraySize;i++)
	{
		heap.heapArray[i] = rand()%101;//产生0到100之间的随机数
	}
	cout << "before heapSort:" << endl;
	print(heap);
	heapSort(heap);
	cout << "after heapSort:" << endl;
	print(heap);

	system("pause >> cout");
	return 0;
}

void exchange(int *x,int *y)
{
	int temp = *x;
	*x = *y;
	*y = temp;
}

//最大堆的性质
void maxHeapify(heapType &h,int i)
{
	int l = 2*i;
	int r = 2*i + 1;
	int subscript = i;
	if(l<=h.heapSize && h.heapArray[subscript]<h.heapArray[l])
		subscript = l;
	if(r<=h.heapSize && h.heapArray[subscript]<h.heapArray[r])
		subscript = r;
	if(subscript!=i)
	{
		cout << "echange the " << i << "th :" << h.heapArray[i] 
		       << " and the " << subscript << "th :" << h.heapArray[subscript] 
			   << endl;
		exchange(&h.heapArray[subscript],&h.heapArray[i]);
		maxHeapify(h,subscript);
	}
}

//对堆（二叉树）而言，从第(heapSize/2+1)开始到第n个元素为叶子节点
void buildMaxHeap(heapType &h)
{
	h.heapSize = h.arraySize;
	for(int i=h.heapSize/2;i>=1;i--)
		maxHeapify(h,i);
}

void heapSort(heapType &h)//堆排序操作
{
	cout << "build the maxHeap:" << endl;
	buildMaxHeap(h);//建最大堆
	cout << "begin the heapSort:" << endl;
	//每一次都将h[i]和h[heapsize]互换，然后进行maxHeapify(h)操作，使满足最大堆
	//接着heapSize = heapSize - 1 
	for(int i=h.heapSize;i>=2;i--)
	{
		exchange(&h.heapArray[1],&h.heapArray[i]);
		h.heapSize = h.heapSize - 1;
		maxHeapify(h,1);
	}
}
void print(heapType &h)
{
	for(int i=1;i<=h.arraySize;i++)
		cout << " " << h.heapArray[i];
	cout << endl;
}