【数据结构学习】-堆与堆排序

旧城等待， 2022-08-04 12:44 152阅读 0赞

堆是一种非常有用的数据结构，可用来设计高效的排序算法和优先队列。一个堆是一颗具有如下性质的二叉树：1）它是一颗完全二叉树；2）每个节点都大于等于其任何子节点。

![Center][]

如上图是一个最大堆，我们可以用数组来描述它。根节点在数组位置0，两个孩子在位置1和2。对于位于位置i的节点，其左孩子在2i+1，其右孩子在2i+2，其父节点在(i-1)/2。利用堆进行排序，是堆一个很重要的用途。下面是堆排序的代码：

#include <iostream>
    using namespace std;
    void adjustHeap(int a[],int size,int index)
    {
    	int left = index*2+1;		//左子节点在数组中的位置
    	int right = index*2+2;		//右子节点在数组中的位置
    	int largest = index;
    	int temp;
    	while(left<size || right<size)		//循环遍历，直到没有子节点为止
    	{
    		if(left<size && a[left]>a[largest])
    		{
    			largest = left;
    		}
    		if(right<size && a[right]>a[largest])
    		{
    			largest = right;
    		}							//找到左右子节点和根节点的最大值
    		if(index!=largest)			//如果根节点不是最大值
    		{
    			temp=a[largest];
    			a[largest]=a[index];
    			a[index]=temp;			//交换子节点和根节点
    			index=largest;			//继续向下遍历，调整堆
    			left=index*2+1;
    			right=index*2+1;
    		}
    		else
    		{
    			break;
    		}
    	}
    }
    void buildHeap(int a[],int size)
    {
    	int begin=size/2-1;		//从该结点往后的值都没有子节点
    	for(int i=begin;i>=0;i--)		//建立最大堆
    	{
    		adjustHeap(a,size,i);
    	}
    }
    void heapSort(int a[],int len)
    {
    	int size=len;
    	int temp;
    	buildHeap(a,size);
    	while(size>1)
    	{
    		temp=a[0];
    		a[0]=a[size-1];
    		a[size-1]=temp;
    		size--;
    		adjustHeap(a,size,0);
    	}
    }
    
    int _tmain(int argc, _TCHAR* argv[])
    {
    	int num[8]={2,8,7,1,3,5,6,4};
    	cout<<"排序前的输出顺序为："<<endl;
    	for(int i=0;i<8;i++)
    	{
    		cout<<num[i]<<"\t";
    	}
    	heapSort(num,8);
    	cout<<endl<<"排序后的输出顺序为:"<<endl;
    	for(int i=0;i<8;i++)
    	{
    		cout<<num[i]<<"\t";
    	}
    	return 0;
    }

输出结果为：  
排序前的输出顺序为：  
2 8 7 1 3 5 6 4  
排序后的输出顺序为:  
1 2 3 4 5 6 7 8

[Center]: /images/20220731/3138eaaca06f4075984b09f11628e936.png