《算法导论》学习总结——第二部分1堆排序-白红宇

《算法导论》学习总结——第二部分1堆排序

阅读量：2439 次

发布时间：2019-05-10

本文共 3056 字，大约阅读时间需要 10 分钟。

堆排序是个很漂亮的算法啊，第一部分讲到了插入排序，归并排序，并实现。这里有2个概念：原地排序（在排序输入数组时，只有常数个元素被放到数组以外的空间中去）；稳定排序（就是相等的两个数，排序前的顺序与排序后的么顺序相同）

说到这个，就扯下吧，稳定排序有：冒泡排序、插入排序、归并排序、基数排序。不稳定排序有：选择排序、快速排序、希尔排序(shell)、堆排序。其中，插入排序，归并排序，堆排序和快速排序都是比较排序（shell看做周期插入）。

这里还提到的顺序统计学（P72）。描述：在一个由n个数构成的集合上，第i个顺序统计是集合中第i小的数。

如图是一个堆，首先，引入PARENT[i]和LEFT[i]以及RIGHT[i]分别表示i的父节点和左右子节点。堆排序的核心三步：1）让A[i]在最大堆中下降，使以i为根的子树成为大顶堆；2）建堆，将当前数组建为一个大顶or小顶堆,注意的就是建堆的时候，从length/2到0，由于根都在length/2范围，且大值影响小值，所以得递减的减（练习6.3-2）；3）进行堆排序。

堆排序的核心，是通过建堆，以大顶堆为例，将最大元素放到根位置，也就是v[0]，再通过输出v0与最后一个元素的交换，再对剩下元素继续建堆，不断得到当前最大值，过程可以看做递归。于是可以得到这三个步骤的实现如下：

void MaxHeapify(vector
   
     &v ,int i ){//让A[i]在最大堆中下降，使以i为根的子树成为大顶堆	int left=2*i+1; //l<-LEFT(i) ，这里i从0开始，所以left和right与伪代码略有出入	int right = 2*i+2; //r<-RIGHT(i)	int largest=i;	if ( (left < v.size())  && (v[left] > v[i]) )		largest = left ; 	else 		largest = i;	if ( (right 
    
      v[largest]) )		largest = right;//从父母和自己中找出最大的	if (largest != i)	{		swap(v[i],v[largest]);//交换使i和子堆满足堆性质，不过largest为根的可能违反，递归调整		MaxHeapify(v,largest);	} }void BuildHeap(vector
     
       &v){//建堆	for (int i=v.size()/2 ; i >= 0 ; i--)		MaxHeapify(v,i);}void HeapSort(vector
      
        &v){ // 对vector进行堆排序	vector
       
         temp(v);	v.clear();	BuildHeap(temp);// 把temp建成大顶堆	for(int i=temp.size()-1 ; i>=0 ; i-- )	{//将堆顶记录和当前未经排序子序列[0..i]中最后一个记录相互交换		swap(temp[0],temp[i]);		v.push_back(temp[i]);//这样排完的v就是大的在前面了		temp.pop_back();			MaxHeapify(temp,0); // 将v[0..i-1]重新调整为大顶堆 	}}

关于这个HeapSort过程，由于伪代码中有数组A的size-1过程，但对v我们需要保存所有值并输出，这里引入临时数组temp，通过temp的pop_back实现size-1，尽可能贴合伪代码，将排序结果通过v的clear和push_back重新添加，保存排序结果。问题只是v是从大到小排序，当然，伪代码中数组从1到length，如果考虑贴近使left=2*i而不是2*i+1的话，可以

v.insert(v.begin(),INT_MAX);

在0的位置插入个值，但是不去使用。不过这样意义不大。

另外，不要忽略建堆过程中的伪代码：heap-size[A]<- length[A]，这是不同的，虽然在代码中体现的不明显，不过仍然得区分这两个概念。

对于size-1 的另一种解决办法，是传参的时候，实现的代码如下：

void MaxHeapify(vector
   
     &v ,int i , int size)//这里size，则是当前大小{//让A[i]在最大堆中下降，使以i为根的子树成为大顶堆	int left=2*i+1; //l<-LEFT(i)	int right = 2*i+2; //r<-RIGHT(i)	int largest=i;	if ( (left < size)  && (v[left] > v[i]) )//比较变为size		largest = left ; 	else 		largest = i;	if ( (right <=size ) && (v[right] > v[largest]) )		largest = right;//从父母和自己中找出最大的	if (largest != i)	{		swap(v[i],v[largest]);//交换使i和子堆满足堆性质，不过largest为根的可能违反，递归调整		MaxHeapify(v,largest,size);	} }void BuildHeap(vector
    
      &v){//建堆	for (int i=v.size()/2 ; i >= 0 ; i--)		MaxHeapify(v,i,v.size()-1); }void HeapSort(vector
     
       &v){	BuildHeap(v);	cout << "v[0] : " << v[0] << endl;	cout << "size : " << v.size()<< endl;	cout << v[v.size()-1] << endl;	for (int i=v.size()-1 ; i>0 ; i--)	{		swap(v[0],v[i]); 		MaxHeapify(v,0,i-1);//传i-1实现size-1，则v不动	}}

当然，对于第一步的调整过程，我们也可以消除递归如下所示：

void MaxHeapify(vector
   
     &v ,int i , int size){//让A[i]在最大堆中下降，使以i为根的子树成为大顶堆	int max,temp=v[i];	for (max = 2*i ; max <= size ; max *= 2)	{//沿key较大的孩子结点向下筛选		if (max < size && v[max] < v[max+1])			max++;		if (temp >= v[max])			break;		v[i] = v[max];		i = max ;	}	v[i] = temp;}

上面这个，不用递归的，也是严蔚敏数据结构的书上的方法。

先总结这些吧，堆排序测试了下，速度仅次于快排，不得不说，还是很给力的。下面是优先级队列。

keep going 。。。

转载地址：http://cocqb.baihongyu.com/

你可能感兴趣的文章