堆:
堆是具有下列性质的完全二叉树:
每个节点的值都大于或等于左右孩子节点的值,称为大顶堆;
每个节点的值都小于或等于左右孩子节点的值,称为小顶堆。
堆排序
#include <iostream>
using namespace std;
/******************堆排序************************/
void AdjustHeap(int arr[], int s, int m) {
int temp = arr[s];
for(int j = 2*s+1; j <= m; j *= 2 + 1) {
if(j < m && arr[j] < arr[j+1])
j++;
if(temp > arr[j])
break;
arr[s] = arr[j];
s = j;
}
arr[s] = temp;
}
void HeapSort(int arr[], int length) {
if(length <= 0)
return;
for(int i = length/2 -1; i >= 0; --i) {
AdjustHeap(arr, i, length-1);
}
for(int i = length -1; i > 0; --i) {
swap(arr[0], arr[i]);
AdjustHeap(arr, 0, i-1);
}
}
网友评论