#H31. 堆排序
堆排序
Background
堆排序的实现
Description
完成下述插入堆代码框架后提交,只需完成注释中的要求,无需输入输出
#include "HeapSort.h"
void HeapSort::max_heapify(std::vector<int>& nums, int i) {
// 请在这里完成你的代码
}
void HeapSort::build_max_heap(std::vector<int>& nums) {
// 请在这里完成你的代码
}
void HeapSort::mysort(std::vector<int>& nums) {
length = nums.size();
nums.insert(nums.begin(), 0); // 在开头插入一个元素,使得待排序元素下标从 1 开始
// 请在这里完成你的代码
nums.erase(nums.begin()); // 删除开头元素
}
Samples
提供一组样例用于自测
6
5 2 4 2 3 1
1 2 2 3 4 5
附HeapSort.h
#pragma once
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <functional>
using namespace std;
class MySort {
public:
virtual void mysort(std::vector<int>& nums) = 0;
};
class HeapSort: public MySort {
public:
int heap_size;
int length;
// 通过堆排序对int数组nums进行升序排序
// @param
// nums: 完整的待排序队列,最终排序的结果应存放在nums中
void mysort(std::vector<int>& nums);
void max_heapify(std::vector<int>& nums, int i);
void build_max_heap(std::vector<int>& nums);
};