最大堆排序

最大堆排序

目录

​​一、基础堆​​

​​二、原地最大堆​​

一、基础堆

基础堆的搭建，将传入的数组数组元素放入一个新的数组，并操作成最大堆

shift Down/shift Up函数，逐个插入元素，或者直接插入数组、终端中以树形结构方式的打印函数的实现

template class MaxHeap{private: Item* data; //堆中已经存放了多少堆元素 int count; //可以存放多少个堆元素 int capacity; //私有属性，对象调用不了，用户调用Insert函数就可以了 void shiftUp(int k) { while (k>1&&data[k] > data[k / 2]) { swap(data[k], data[k / 2]); k /= 2; } } //如果有左右孩子，则找出左右孩子的最大值索引，跟父节点比较，如果父节点比他们大，则跳出，反之则交换 void shiftDown(int k) { while (2 * k <= count) { //j存放孩子的最大值索引，默认为左孩子 int j = 2 * k; //要考虑j边界问题 if (j + 1 <= count && data[j + 1] > data[j]) { j += 1; } if (data[k] >= data[j]) break; swap(data[k], data[j]); k = j; } } //在控制台中打印树型辅助函数 void putNumberInLine(int num, string &line, int index_cur_level, int cur_tree_width, bool isLeft) { int sub_tree_width = (cur_tree_width - 1) / 2; int offset = index_cur_level * (cur_tree_width + 1) + sub_tree_width; assert(offset + 1 < line.size()); if (num >= 10) { line[offset + 0] = '0' + num / 10; line[offset + 1] = '0' + num % 10; } else { if (isLeft) line[offset + 0] = '0' + num; else line[offset + 1] = '0' + num; } } //在控制台中打印树型辅助函数 void putBranchInLine(string &line, int index_cur_level, int cur_tree_width) { int sub_tree_width = (cur_tree_width - 1) / 2; int sub_sub_tree_width = (sub_tree_width - 1) / 2; int offset_left = index_cur_level * (cur_tree_width + 1) + sub_sub_tree_width; assert(offset_left + 1 < line.size()); int offset_right = index_cur_level * (cur_tree_width + 1) + sub_tree_width + 1 + sub_sub_tree_width; assert(offset_right < line.size()); line[offset_left + 1] = '/'; line[offset_right + 0] = '\\'; }public: MaxHeap(int capacity) { //因为堆的根节点索引从1开始 data = new Item[capacity+1]; count = 0; this->capacity = capacity; } //heapify的过程，算法复杂度为O(n)，将n个元素逐个插到一个空堆中，算法复杂度是O(nlogn) MaxHeap(Item arr[],int n) { data = new Item[n + 1]; for (int i = 0; i < n; i++) { data[i + 1] = arr[i]; } count = n; capacity = n; for (int i = count / 2; i >= 1; i--) shiftDown(i); } ~MaxHeap() { delete[] data; } int size() { return count; } bool isEmpty() { return count == 0; } //给堆插入元素 void Insert(Item item) { assert(count + 1 <= capacity); data[count + 1] = item; count++; shiftUp(count); } //从堆中提取元素，数组中堆以外的元素不是为空，而是有值得数，是从根节点替换下来的 Item extractMax() { assert(count >=1); Item pop = data[1]; swap(data[1], data[count]); count--; shiftDown(1); return pop; } //在控制台中打印树型函数 void testPrint() { if (size() >= 100) { cout << "Fancy print can only work for less than 100 int"; return; } if (typeid(Item) != typeid(int)) { cout << "Fancy print can only work for int item"; return; } cout << "The Heap size is: " << size() << endl; cout << "data in heap: "; for (int i = 1; i <= size(); i++) cout << data[i] << " "; cout << endl; cout << endl; int n = size(); int max_level = 0; int number_per_level = 1; while (n > 0) { max_level += 1; n -= number_per_level; number_per_level *= 2; } int max_level_number = int(pow(2, max_level - 1)); int cur_tree_max_level_number = max_level_number; int index = 1; for (int level = 0; level < max_level; level++) { string line1 = string(max_level_number * 3 - 1, ' '); int cur_level_number = min(count - int(pow(2, level)) + 1, int(pow(2, level))); bool isLeft = true; for (int index_cur_level = 0; index_cur_level < cur_level_number; index++, index_cur_level++) { putNumberInLine(data[index], line1, index_cur_level, cur_tree_max_level_number * 3 - 1, isLeft); isLeft = !isLeft; } cout << line1 << endl; if (level == max_level - 1) break; string line2 = string(max_level_number * 3 - 1, ' '); for (int index_cur_level = 0; index_cur_level < cur_level_number; index_cur_level++) putBranchInLine(line2, index_cur_level, cur_tree_max_level_number * 3 - 1); cout << line2 << endl; cur_tree_max_level_number /= 2; } }};templatevoid heapsort(T arr[],int n){ MaxHeap maxheap = MaxHeap(arr, n); for (int i = n - 1; i >= 0; i--) { arr[i] = maxheap.extractMax(); }}

shiftDown传统的比较三个值大小的写法

void shiftDown(int k) { if (2 * k <= count) { Item max = data[k]; Item maxindex = k; if (data[2 * k] > max) { max = data[2 * k]; maxindex = 2 * k; } //注意j的边界取值 if (data[2 * k + 1] > max && 2 * k + 1 <= count) { max = data[2 * k + 1]; maxindex = 2 * k + 1; } //如果父节点比子节点大则不需要交换 if (max != data[k]) { swap(data[k], data[maxindex]); shiftDown(maxindex); } } }

二、原地最大堆

根的索引为0，有n个元素，最后一个非叶子节点索引为 （n-1-1）/2

//T arr[] 数组，n为数组arr中元素的个数，k是需要执行shiftDown操作的索引templatevoid __shiftDown(T arr[], int n, int k) { while (2 * k + 1 < n) { //堆的根索引为0时，左孩子为 2 * k + 1，默认左孩子为最大值 int j = 2 * k + 1; if (j + 1 < n &&arr[j + 1] > arr[j]) j += 1; if (arr[k] >= arr[j])break; swap(arr[k], arr[j]); k = j; }}//T arr[] 传递的数组，n为数组的元素大小templatevoid heapSort(T arr[], int n) {//根的索引为0，有n个元素，最后一个非叶子节点索引为 （n-1-1）/2 for (int i = (n-2) / 2; i >= 0; i--) __shiftDown(arr, n, i); for (int i = n - 1; i > 0; i--) { swap(arr[0], arr[i]); __shiftDown(arr, i, 0); }}

C++堆排序代码

#include#includeusing namespace std;////T arr[] 数组，n为数组arr中元素的个数，k是需要执行shiftDown操作的索引void __shiftDown(vector& arr, int n, int k) { while (2 * k + 1 < n) { //堆的根索引为0时，左孩子为 2 * k + 1，默认左孩子为最大值 int j = 2 * k + 1; if (j + 1 < n && arr[j + 1] > arr[j]) j += 1; //本身父节点就是大于 子节点 所以什么都不做，直接跳出 if (arr[k] >= arr[j])break; swap(arr[k], arr[j]); //交换的是j，将j赋值给k，一直shift_down下去，维持最大堆 k = j; }}//T arr[] 传递的数组，n为数组的元素大小templatevoid heapSort(vector& arr, int n) { //根的索引为0，有n个元素，最后一个非叶子节点索引为 （n-1-1）/2 for (int i = (n - 2) / 2; i >= 0; i--) __shiftDown(arr, n, i); for (int i = n - 1; i > 0; i--) { cout << arr[0] << " "; swap(arr[0], arr[i]); __shiftDown(arr, i, 0); }}int main(void) { vector arr = { 4,3,6,45,3,2,7,8,5,4 }; heapSort(arr, 10); return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。