二叉堆:
二叉堆是完全二叉树或者是近似完全二叉树。
二叉堆满足二个特性:
1.父结点的键值总是大于或等于(小于或等于)任何一个子节点的键值。
2.每个结点的左子树和右子树都是一个二叉堆(都是最大堆或最小堆)。
当父结点的键值总是大于或等于任何一个子节点的键值时为最大堆。当父结点的键值总是小于或等于任何一个子节点的键值时为最小堆
实现:
/************************************************ 堆排序 by Rowandjj 2014/7/23 ************************************************/ #include<iostream> using namespace std; //数组arr,除了start位置上的元素不满足大顶堆的性质, //其他元素均满足,此函数的作用是使数组从start到end都满足大顶堆的性质 void HeapAdjust(int arr[],int start,int end) { int temp = arr[start];//记录不满足大顶堆性质的元素 int i = start*2+1;//i为其左孩子序号 while(i<=end) { if(i+1<=end && arr[i+1]>arr[i])//获取左右孩子较大的孩子的序号(如果有右孩子的话) { i++; } if(temp >= arr[i])//如果满足大顶堆性质那么无须操作 { break; } arr[start] = arr[i];//否则最大的子节点向上移动,替换掉其父节点 start = i;//判断其子树是否满足大顶堆性质 i = i*2+1; } arr[start] = temp; } void HeapSort(int arr[],int len) { if(arr == NULL || len <= 0) { return; } int i; for(i = len/2-1; i >= 0; i--)//将无序数组构建成大顶堆,从第一个非叶子节点开始建堆 { HeapAdjust(arr,i,len-1); } for(i = len-1; i > 0; i--)//每次都将堆顶元素(最大元素)与堆尾元素互换,然后去掉堆尾元素,对其他元素进行建堆操作 { int temp = arr[i]; arr[i] = arr[0]; arr[0] = temp; HeapAdjust(arr,0,i-1); } } int main() { int arr[] = {6,1,3,1,5,4,2,7}; HeapSort(arr,8); for(int i = 0; i < 8; i++) { cout<<arr[i]<<" "; } cout<<endl; return 0; }
原文:http://blog.csdn.net/chdjj/article/details/38071439