堆排序（最大堆）

我不是女神ヾ 2022-06-09 12:25 260阅读 0赞

## **基本概念** ##

**数据结构：记录=关键值+卫星数据**

**关键值：待排序的值**

**卫星数据：与关键值一同存取**

**原址排序：输入数组中仅有常数个（少量）元素需要在排序过程中存储在数组之外（额外空间村存储临时数据）。**

**   堆排序**，**[归并排序][Link 1]**在最坏情况下都是时间复杂度为O(N\*logN)的排序方法，[快速排序][Link 2]与**归并排序**在平均情况下时间复杂度是O（nlgn）。

学习堆排序前，先讲解下什么是数据结构中的二叉堆。

##  ##

## 二叉堆的定义 ##

**二叉堆是完全二叉树（堆的高度是olg(n)）**或者是近似完全二叉树。树上的每一个节点对应数组中的一个元素。

二叉堆满足二个**特性**：

1．父结点的键值总是大于或等于（小于或等于）任何一个子节点的键值。

2．每个结点的左子树和右子树都是一个二叉堆（都是最大堆或最小堆）。

当父结点的键值总是大于或等于任何一个子节点的键值时为**最大堆**。当父结点的键值总是小于或等于任何一个子节点的键值时为**最小堆**。**堆排序**使用的是**最大堆**，**最小堆**用于构造**优先队列**。

下图展示一个最小堆：

![0_1314014666d5oe.gif][]

由于其它几种堆（二项式堆，斐波纳契堆等）用的较少，一般将**二叉堆就简称为堆**。

##  ##

## 堆的存储 ##

**一般都用数组来表示堆**，i结点的父结点下标就为(i – 1) / 2。它的左右子结点下标分别为2 \* i + 1和2 \* i + 2。如第0个结点左右子结点下标分别为1和2。

![0_1314014706gZqn.gif][]

## **堆的基本过程** ##

**1、MAX-HEAPIFY过程：其时间复杂度为o（lgn），它是维护最大堆性质的关键。**

**2、BUILD-MAX-HEAP过程：具有线性时间复杂度，功能是从无序的输入数据数组中构造一个最大堆。**

**3、HEAPSORT过程：其时间复杂度为o（nlgn），功能是对一个数组进行原址排序。**

**4、MAX-HEAP-INSERT HEAP\[-EXTRACT-MAX HEAP-INCREASE-KEY HEAP-MAXIMUM过程：时间复杂度为o（lgn），功能是利用堆实现一个优先队列。**

##     ##

## **维护堆性质**：MAX-HEAPIFY伪代码 ##

MAX-HEAPIFY
     l=LEFT(i)
     r=RIGHT(i)
     if l<=A.heap-size and A[l]>A[i]
        largest=l
     else largest=r
     if r<=A.heap-size and A[r]>A[largest]
        largest=r
     if largest!=i
        exchange A[i] with A[largest]
        MAX-HEAPIFY（A,largest）

**建堆:**

BUILD-MAX-HEAPIFY（A）
      A.heap-size=A.length
      for i=[A.length/2]downto 1
         MAX-HEAPIFY(A,i)

**堆排序算法：**

HEAPSORT（A）
      BUILD-MAX-HEAP（A）
      for i=A.length downto 2
          exchange A[1] with A[i]
          A.heap-size=A.heap-size-1
          MAX-HEAPIFY(A,1)

##  ##

**示例：**

#include<iostream> using namespace std; //维持最大堆性质 //序号第i个根节点下左右子节点 void max_heapify(int*a,int i,int n) { int l = 2 * i; //左子节点 int r = 2 * i + 1,largest; //右子节点 if (l <n&&a[l] > a[i]) //左子节点>根节点 largest = l; //记录最大值的序号 else largest = i; if (r <n&&a[r] > a[largest])//右子节点>最大值 largest=r; if (largest != i) //若largest=i,不需要操作，不满足，则交换且以largest序号为根节点继续进行判断 { int temp = a[i]; a[i] = a[largest]; a[largest] = temp; max_heapify(a, largest, n); } } //建堆：创建一个最大堆 void build_max_heap(int*a, int n) { for (int i = n / 2-1; i >= 0; i--) max_heapify(a, i, n); } //堆排序 void heapsort(int *a, int n) { build_max_heap(a, n); for (int i = n-1; i > 0; i--) { int temp = a[0]; a[0] = a[i]; a[i] = temp; n--; max_heapify(a, 0, n); } } void Print(int *a,int n) { int i = 0; for (; i < n; i++) cout << a[i] << " "; cout << endl; } int main() { int a[10] = { 4, 1, 3, 2, 19, 9, 10, 14, 8, 7 }; Print(a, 10); heapsort(a, 10); Print(a, 10); system("pause"); return 0; }

## 堆的操作——插入删除 ##

![0_131415207877s7.gif][]

### 堆的插入 ###

**伪代码：**

MAX-HEAP-INSERT（A,key） A.heap-size=A.heap-size+1 A[A.heap-size]=-oo HEAP-INCREASE-KEY（A,A.heap-size，key）

**每次插入都是将新数据放在数组最后**。可以发现从这个新数据的父结点到根结点必然为一个有序的数列，现在的任务是将这个新数据插入到这个有序数据中——这就类似于**直接插入排序**中将一个数据并入到有序区间中，插入一个新数据时堆的调整代码：

#include<iostream> using namespace std; void max_heapify(int*a, int i, int n);//堆性质维护 void build_max_heap(int*a, int n);//建堆 void heapsort(int *a, int n);//堆排序 void MinHeapFixup(int a[], int i);//堆重组 void MinHeapAddNumber(int a[], int n, int nNum);//堆中加入数据 void Print(int *a, int n);//打印数组 //维持最大堆性质 //序号第i个根节点下左右子节点 void max_heapify(int*a,int i,int n) { int l = 2 * i; //左子节点 int r = 2 * i + 1,largest; //右子节点 if (l <n&&a[l] > a[i]) //左子节点>根节点 largest = l; //记录最大值的序号 else largest = i; if (r <n&&a[r] > a[largest])//右子节点>最大值 largest=r; if (largest != i) //若largest=i,不需要操作，不满足，则交换且以largest序号为根节点继续进行判断 { int temp = a[i]; a[i] = a[largest]; a[largest] = temp; max_heapify(a, largest, n); } } //建堆：创建一个最大堆 void build_max_heap(int*a, int n) { for (int i = n / 2-1; i >= 0; i--) max_heapify(a, i, n); cout << "创建好的堆数据：" << endl; Print(a, n); //在已建堆中即数组最后插入新数据 MinHeapAddNumber(a, 10, 11); //堆重组结果 cout << "堆重组结果：" << endl; Print(a, 11); } //堆排序 void heapsort(int *a, int n) { build_max_heap(a, n); for (int i = n-1; i > 0; i--) { int temp = a[0]; a[0] = a[i]; a[i] = temp; n--; max_heapify(a, 0, n); } } // 新加入i结点 其父结点为(i - 1) / 2 void MinHeapFixup(int a[], int i) { int j, temp; temp = a[i]; j = (i - 1) / 2; //父结点 while (j >= 0 && i != 0) { if (a[j] >= temp)//判断新插入数据的父节点与该数据的大小 break; a[i] = a[j]; //把小的子结点往下移动,替换它的子结点 i = j; j = (i - 1) / 2; } a[i] = temp; } //在最小堆中加入新的数据nNum void MinHeapAddNumber(int a[], int n, int nNum) { a[n] = nNum; cout << "插入数据:" << endl; Print(a, n+1); MinHeapFixup(a, n); } void Print(int *a,int n) { int i = 0; for (; i < n; i++) cout << a[i] << " "; cout << endl; } int main() { int a[11] = { 4, 1, 3, 2, 19, 9, 10, 14, 8, 7 }; cout << "原始数据:" << endl; Print(a, 11); heapsort(a, 11); cout << "堆排序结果：" << endl; Print(a, 11); system("pause"); return 0; }

### 堆的删除 ###

按定义，**堆中每次都只能删除第0个数据。**为了便于重建堆，实际的操作是将最后一个数据的值赋给根结点，然后再从根结点开始进行一次从上向下的调整。调整时先在左右儿子结点中找最大的，如果父结点比这个最大的子结点还大说明不需要调整了，反之将父结点和它交换后再考虑后面的结点。相当于从根结点将一个数据的“下沉”过程。下面给出代码：

#include<iostream>
    using namespace std;
    
    void MAX_HEAPIFY(int*a, int i, int n);//堆性质维护
    void BUILD_MAX_HEAP(int*a, int n);//建堆
    void HEAPSORT(int *a, int n);//堆排序
    void MaxHeapFixup(int a[], int i);//最大堆向上调整
    void MaxHeapAddNumber(int a[], int n, int nNum);//堆中加入数据
    void MaxHeapFixdown(int a[], int i, int n);//最大堆向下调整
    void MaxHeapDeleteNumber(int a[], int n);//最大堆删除数字
    void Print(int *a, int n);//打印数组
    
    //维持最大堆性质
    //序号第i个根节点下左右子节点
    void MAX_HEAPIFY(int*a,int i,int n)
    {
    	int l = 2 * i;              //左子节点
    	int r = 2 * i + 1,largest;  //右子节点
    	if (l <n&&a[l] > a[i])      //左子节点>根节点
    		largest = l;            //记录最大值的序号为l
    	else
    		largest = i;
    	if (r <n&&a[r] > a[largest])//右子节点>最大值记录
    		largest=r;
    	if (largest != i)            //若largest=i（即原根节点值最大）,不需要操作，不满足，则交换且
    	{
    		int temp = a[i];
    		a[i] = a[largest];
    		a[largest] = temp;
    		MAX_HEAPIFY(a, largest, n);//以largest序号为根节点继续进行判断
    	}
    
    }
    
    //建堆：创建一个最大堆
    void BUILD_MAX_HEAP(int*a, int n)
    {
    	for (int i = n / 2-1; i >= 0; i--)
    		MAX_HEAPIFY(a, i, n);
    	cout << "创建好的堆数据：" << endl;
    	Print(a, n);
    	//在已建堆中即数组最后插入新数据
    	MaxHeapAddNumber(a, 10, 11);
    	//堆重组结果
    	cout << "插入后堆重组结果：" << endl;
    	Print(a, 11);
    
    	MaxHeapDeleteNumber(a,11);
    	cout << "删除后堆重组结果：" << endl;
    	a[10] = 0;  //删除首元素放置最后一个重新赋值为0加以区分。
    	Print(a, 11);
    	
    }
    
    //堆排序
    void HEAPSORT(int *a, int n)
    {
    	BUILD_MAX_HEAP(a, n);
    	for (int i = n-1; i > 0; i--)
    	{
    		int temp = a[0];
    		a[0] = a[i];
    		a[i] = temp;
    		n--;
    		MAX_HEAPIFY(a, 0, n);
    	}
    
    }
             //*****插入****/
    //  新加入i结点  其父结点为(i - 1) / 2  
    void MaxHeapFixup(int a[], int i)
    {
    	int j, temp;
    
    	temp = a[i];
    	j = (i - 1) / 2;      //父结点  
    	while (j >= 0 && i != 0)
    	{
    		if (a[j] >= temp)//判断新插入数据的父节点与该数据的大小
    			break;
    
    		a[i] = a[j];     //把小的子结点往下移动,替换它的子结点  
    		i = j;
    		j = (i - 1) / 2;
    	}
    	a[i] = temp;
    }
    
    //在最大堆中加入新的数据nNum  
    void MaxHeapAddNumber(int a[], int n, int nNum)
    {
    	
    	a[n] = nNum;
    	cout << "插入数据:" << endl;
    	Print(a, n+1);
    	MaxHeapFixup(a, n);
    }
    
              //********删除********//
    //  从i节点开始调整,n为节点总数 从0开始计算 i节点的子节点为 2*i, 2*i+1  
    void MaxHeapFixdown(int a[], int i, int n)
    {
    	int j, temp;
    
    	temp = a[i];   //父节点
    	j = 2 * i ; //左子节点序号
    	while (j < n)
    	{
    		if (j + 1 < n && a[j + 1] >a[j]) //在左右孩子中找最大的  
    			j++;
    
    		if (a[j] <= temp)
    			break;
    
    		a[i] = a[j];     //把大的子结点往上移动,替换它的父结点  
    		i = j;
    		j = 2 * i+1;
    	}
    	a[i] = temp;
    }
    //在最大堆中删除第n个数  
    void MaxHeapDeleteNumber(int a[], int n)
    {
    	int temp = a[0];
    	a[0] = a[n - 1];
    	a[n - 1] = temp;
    	MaxHeapFixdown(a, 0, n - 1);
    }
    
    
    
    void Print(int *a,int n)
    {
    	int i = 0;
    	for (; i < n; i++)
    		cout << a[i] << " ";
    	cout << endl;
    }
    
    
    int main()
    {
    	int a[11] = { 4, 1, 3, 2, 19, 9, 10, 14, 8, 7 };
    	cout << "原始数据:" << endl;
    	Print(a, 11);
    	HEAPSORT(a, 11);
    	cout << "堆排序结果：" << endl;
    	Print(a, 11);
    
    	system("pause");
    	return 0;
    }

## 堆化数组 ##

有了堆的插入和删除后，再考虑下如何对一个数据进行堆化操作。要一个一个的从数组中取出数据来建立堆吧，不用！先看一个数组，如下图：

![0_1314014725K5k6.gif][]

很明显，对叶子结点来说，可以认为它已经是一个合法的堆了即20，60， 65， 4， 49都分别是一个合法的堆。只要从A\[4\]=50开始向下调整就可以了。然后再取A\[3\]=30，A\[2\] = 17，A\[1\] = 12，A\[0\] = 9分别作一次向下调整操作就可以了。下图展示了这些步骤：

![0_1314014735kbBA.gif][]

写出堆化数组的代码：

**\[cpp\]**  [view plain][]   [copy][view plain]

1.  //建立最小堆  
2.  **void** MakeMinHeap(**int** a\[\], **int** n)  
3.  \{  
4.      **for** (**int** i = n / 2 - 1; i >= 0; i--)  
5.          MinHeapFixdown(a, i, n);  
6.  \}

至此，堆的操作就全部完成了(注1)，再来看下如何用堆这种数据结构来进行排序。

## 堆排序 ##

首先可以看到堆建好之后堆中第0个数据是堆中最小的数据。取出这个数据再执行下堆的删除操作。这样堆中第0个数据又是堆中最小的数据，重复上述步骤直至堆中只有一个数据时就直接取出这个数据。

由于堆也是用数组模拟的，故堆化数组后，第一次将A\[0\]与A\[n - 1\]交换，再对A\[0…n-2\]重新恢复堆。第二次将A\[0\]与A\[n – 2\]交换，再对A\[0…n - 3\]重新恢复堆，重复这样的操作直到A\[0\]与A\[1\]交换。由于每次都是将最小的数据并入到后面的有序区间，故操作完成后整个数组就有序了。有点类似于**[直接选择排序][Link 3]**。

**\[cpp\]**  [view plain][]   [copy][view plain]

1.  **void** MinheapsortTodescendarray(**int** a\[\], **int** n)  
2.  \{  
3.      **for** (**int** i = n - 1; i >= 1; i--)  
4.      \{  
5.          Swap(a\[i\], a\[0\]);  
6.          MinHeapFixdown(a, 0, i);  
7.      \}  
8.  \}

注意使用最小堆排序后是递减数组，要得到递增数组，可以使用最大堆。

由于每次重新恢复堆的时间复杂度为O(logN)，共N - 1次重新恢复堆操作，再加上前面建立堆时N / 2次向下调整，每次调整时间复杂度也为O(logN)。二次操作时间相加还是O(N \* logN)。故堆排序的时间复杂度为O(N \* logN)。STL也实现了堆的相关函数，可以参阅《[STL系列之四 heap 堆][STL_ heap]》。

[Link 1]: http://blog.csdn.net/morewindows/article/details/6678165
[Link 2]: http://blog.csdn.net/morewindows/article/details/6684558
[0_1314014666d5oe.gif]: /images/20220609/b51d81dbf6494b6babdc2856ff025d35.png
[0_1314014706gZqn.gif]: /images/20220609/b3bbd5af7876406fb237f222c337e304.png
[0_131415207877s7.gif]: /images/20220609/d2a8a3e49e9f44ca8660ecf21f9d537a.png
[0_1314014725K5k6.gif]: /images/20220609/bdbe242c75504f89977e83d80e256565.png
[0_1314014735kbBA.gif]: /images/20220609/c259dc51ac4a43558f7fd62b28c413d4.png
[view plain]: http://blog.csdn.net/morewindows/article/details/6709644#
[Link 3]: http://blog.csdn.net/morewindows/article/details/6671824
[STL_ heap]: http://blog.csdn.net/morewindows/article/details/6967409