Skip to content

Instantly share code, notes, and snippets.

@RinChanNOWWW
Created April 16, 2021 00:51
Show Gist options
  • Save RinChanNOWWW/d38a8db020cd8c4c69e1edff54c0b661 to your computer and use it in GitHub Desktop.
Save RinChanNOWWW/d38a8db020cd8c4c69e1edff54c0b661 to your computer and use it in GitHub Desktop.
Heap sort written in C++
#include <iostream>
#include <utility>
#include <vector>
using namespace std;
void adjustHeap(vector<int>& v, int l, int r) {
int val = v[l];
for (int i = l * 2 + 1; i < r; i = i * 2 + 1) {
if (i + 1 < r && v[i] < v[i + 1]) {
i++;
}
if (v[i] > val) {
v[l] = v[i];
l = i;
} else {
break;
}
}
v[l] = val;
}
void heapSort(vector<int>& v) {
for (int i = v.size() / 2 - 1; i >= 0; i--) {
adjustHeap(v, i, v.size());
}
for (int i = v.size() - 1; i > 0; i--) {
swap(v[0], v[i]);
adjustHeap(v, 0, i);
}
}
void printVector(vector<int> v) {
for (auto n : v) {
cout << n << " ";
}
cout << endl;
}
int main() {
vector<int> test{5, 2, 5, 6, 1, 7, 3, 73, 2, 82, 2, 3};
heapSort(test);
printVector(test);
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment