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

知识点：

二叉树：

      任意节点 i，其父节点为（i+1）/2-1

      左孩子节点为 2*i+1

      右孩子节点为 2*i+2

堆排序：

       堆排序比快速排序慢些，但是，有一点它却比快速排序要好很多：最坏情况它的复杂度仍然会保持O(N logN)

      堆是完全二叉树结构，用数组实现。根节点的下标为0。

      最关键是AdjustHeap（）函数，此函数实现大顶堆或小顶堆操作，输入是：存放堆的数组，子树的根节点索引，堆的大小。调整过程是，从子树的根节点往下调整。如果子树存在左右孩子节点，判断孩子节点是否比子树根节点大，若大，则交换，否则就退出。一旦出现交换，那么也需要对以交换的节点为根节点的子树进行递归调整。

      1、初始化堆，初始化是从最后一个叶子节点的父节点开始，然后逐次往上，直到根节点。

      2、进行size-1次循环，因为最后一个元素不用排序就是有序的。

      3、每次循环先将堆顶元素和未排序堆的最后一个元素交换。

      4、更新未排序堆的大小（每次减一，初始为size）。

      5、对根节点调用AdjustHeap（）函数

#include
   
    using namespace std;void swap(int &a, int &b){	int temp;	temp = a;	a = b;	b = temp;}void AdjustHeap(int *heap, int i, int len)  //大顶堆,实现的是升序排序{	int left = i * 2 + 1;   //根节点下标为0，也就是节点是从0开始编号	int right = i * 2 + 2;   //左右节点，分别为2i+1,2i+2	int max = i;	if (left
    
     heap[max]) max = left; //用left和right是否小于len判断孩子节点是否存在	if (right
     
      heap[max]) max = right;	if (max != i)	{		swap(heap[i], heap[max]);		AdjustHeap(heap, max, len);	}}void BuildHeap(int *heap, int len){	for (int i = len / 2 - 1; i >= 0; i--)	{		AdjustHeap(heap, i, len);	}}void sort_heap(int *heap, int len){	BuildHeap(heap, len);	int size = len;	for (int i = 0; i < len - 1; i++)	{		swap(heap[0], heap[size - 1]);		size--;		AdjustHeap(heap, 0, size);	}}int main(){	int a[9] = { 2, 4, 5, 2, 8, 19, 4, 11, 43 };	for (int i = 0; i < 9; i++)	{		cout << a[i] << ' ';	}	cout << endl;	sort_heap(a, 9);	for (int i = 0; i < 9; i++)	{		cout << a[i] << ' ';	}	system("pause");	return 0;}
     
    
   

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