template<typename T>
void maxHeapify(T arr[], int index, int heapSize) {
int maxIndex = index;
int left = 2 * index + 1;
int right = left + 1;
if (left < heapSize && arr[index] < arr[left]) {
maxIndex = left;
}
if (right < heapSize && arr[maxIndex] < arr[right]) {
maxIndex = right;
}
if (maxIndex != index) {
swap(arr[maxIndex], arr[index]);
maxHeapify(arr, maxIndex, heapSize);
}
return;
}
template<typename T>
void build(T arr[], int heapSize) {
for (int i = heapSize / 2 - 1; i >= 0; i--) {
maxHeapify(arr, i, heapSize);
}
}
template<typename T>
void sort(T arr[], int heapSize) {
build(arr, heapSize);
for (int i = heapSize - 1; i > 0; i--) {
swap(arr[0], arr[i]);
maxHeapify(arr, 0, i);
}
}
template<typename T>
void swap(T &a, T &b) {
T temp = a;
a = b;
b = temp;
}
C++的堆排序
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
- 文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
推荐阅读更多精彩内容
- 上一篇C++基础入门之模板堆排序(上):模板上的list的创造与操作 其实接下来就很简单了，只要把大众版的堆排序翻...
- 选择排序 对于任何输入，时间为O(n*n)； 冒泡排序 最优（对于升序的数组，因为加入了一个跳出判断）：O(n)，...
- 整段源码链接C++的模板元堆排序 要点 组建数据结构list 组建对list的各种基本操作 堆排序中组建堆排序个个...
