124 lines
3.0 KiB
C++
124 lines
3.0 KiB
C++
// 版权所有 (c) ling 保留所有权利。
|
||
// 除非另行说明，否则仅允许在DataStruct中使用此文件中的代码。
|
||
//
|
||
// 由 ling 创建于 24-6-30.
|
||
//
|
||
|
||
#ifndef DATASTRUCT_HEAPSORT_H_19
|
||
#define DATASTRUCT_HEAPSORT_H_19
|
||
|
||
#include <vector>
|
||
|
||
namespace ling {
|
||
/**
|
||
* 堆排序
|
||
*/
|
||
template<typename T>
|
||
class HeapSort {
|
||
private:
|
||
std::vector<T> *list;
|
||
|
||
protected:
|
||
virtual bool isBig(const T &, const T &) const = 0;
|
||
|
||
[[nodiscard]] inline bool isLeft(const int i) const {
|
||
return left(i) < list->size();
|
||
}
|
||
|
||
[[nodiscard]] inline bool isRight(const int i) const {
|
||
return right(i) < list->size();
|
||
}
|
||
|
||
[[nodiscard]] static inline int parent(const int i) {
|
||
return (i - 1) / 2;
|
||
}
|
||
|
||
[[nodiscard]] static inline int left(const int i) {
|
||
return i * 2 + 1;
|
||
}
|
||
|
||
[[nodiscard]] static inline int right(const int i) {
|
||
return i * 2 + 2;
|
||
}
|
||
|
||
/// 上滤
|
||
void top(int i) {
|
||
while (i > 0 && isBig((*list)[i], (*list)[parent(i)])) {
|
||
std::swap((*list)[i], (*list)[parent(i)]);
|
||
i = parent(i);
|
||
}
|
||
}
|
||
|
||
/// 下滤
|
||
void bottom(int i, const int size) {
|
||
while (true) {
|
||
int largest = i;
|
||
int l = left(i);
|
||
int r = right(i);
|
||
if (l < size && isBig((*list)[l], (*list)[largest])) {
|
||
largest = l;
|
||
}
|
||
if (r < size && isBig((*list)[r], (*list)[largest])) {
|
||
largest = r;
|
||
}
|
||
|
||
if (largest != i) {
|
||
std::swap((*list)[i], (*list)[largest]);
|
||
i = largest;
|
||
} else {
|
||
break;
|
||
}
|
||
}
|
||
}
|
||
|
||
void bottom(int i) {
|
||
const int size = list->size();
|
||
bottom(i, size);
|
||
}
|
||
|
||
public:
|
||
virtual ~HeapSort() = default;
|
||
|
||
explicit HeapSort(std::vector<T> &list) {
|
||
this->list = &list;
|
||
if (this->list->size() <= 1)
|
||
return;
|
||
}
|
||
|
||
void init() {
|
||
for (int i = parent(list->size() - 1); i >= 0; --i) {
|
||
bottom(i);
|
||
}
|
||
}
|
||
|
||
void insert(T val) {
|
||
list->push_back(std::move(val));
|
||
top(list->size() - 1);
|
||
}
|
||
|
||
void sort() {
|
||
int n = list->size();
|
||
for (int i = n - 1; i > 0; --i) {
|
||
std::swap((*list)[0], (*list)[i]);
|
||
bottom(0, i);
|
||
}
|
||
}
|
||
|
||
};
|
||
|
||
template<typename T>
|
||
class HeapSortDefault final : public HeapSort<T> {
|
||
protected:
|
||
bool isBig(const T &t, const T &t1) const override {
|
||
return t > t1;
|
||
}
|
||
|
||
public:
|
||
explicit HeapSortDefault(std::vector<T> &list) : HeapSort<T>(list) {
|
||
}
|
||
};
|
||
|
||
} // ling
|
||
|
||
#endif //DATASTRUCT_HEAPSORT_H_19
|