堆排序的C++相关实现

大根堆的实现

#include <iostream>
#include <vector>
using namespace std;// 调整堆，确保以i根节点的子树满足大根堆
void heapify(vector<int>& vec, int n , int i) {int largest = i;int left = 2 * i + 1;int right = 2 * i + 2;if (left < n && vec[left] > vec[largetst]) {largest = left;}if (right < n && vec[right] > vec[largetst]) {largest = right;}if (largetst != i) {swap(vec[largest], vec[i]);heapify(vec, n, largest);}
}void sort(vector<int>& vec) {int n = vec.size();for (int i=(n-1)/2; i>=0; --i) {heapify(vec, n, i);}for (int i=n-1; i>=0; --i) {swap(vec[0], vec[i]);heapify(vec, i, 0);}
}
int main() {vector<int> vec = {4,5,6,7,1,9,0};sort(vec);for (auto v: vec) {cout<<v<<" ";}   
}

优先队列，大根堆的实现

#include <iostream>
#include <vector>
using namespace std;class PriorityQueue {
private:vector<int> heap;// 调整堆，从下到上void heapifyUp(int index) {while (index > 0) {int parent = (index - 1) / 2;if (heap[index] > heap[parent]) {swap(heap[index], heap[parent]);index = parent;} else {break;}}}// 调整堆，从上到下void heapifyDown(int index) {int size = heap.size();while (index < size) {int largest = index;int left = 2 * index + 1;int right = 2 * index + 2;if (left < size && heap[left] > heap[largest]) {largest = left;}if (right < size && heap[right] > heap[largest]) {largest = right;}if (largest != index) {swap(heap[largest], heap[index]);index = largest;} else {break;}}}public:void push(int val) {heap.push_back(val);heapifyUp(heap.size() - 1);}void pop() {if (heap.empty()) {std::cerr << "queue empty" << std::endl;return;}swap(heap[0], heap[heap.size()-1]);heapifyDown(0);}int top() {if (heap.empty()) {std::cerr << "queue empty" << std::endl;return -1;}return heap[0];}bool empty() {return heap.empty();}};int main() {PriorityQueue pq;pq.push(10);pq.push(20);pq.push(15);pq.push(30);pq.push(40);std::cout << "优先队列的顶部元素: " << pq.top() << std::endl; // 输出最大元素pq.pop(); // 删除最大元素std::cout << "删除最大元素后，顶部元素: " << pq.top() << std::endl;return 0;
}