C++のスタックソート
997 ワード
template
void maxHeapify(T arr[], int index, int heapSize) {
int maxIndex = index;
int left = 2 * index + 1;
int right = left + 1;
if (left < heapSize && arr[index] < arr[left]) {
maxIndex = left;
}
if (right < heapSize && arr[maxIndex] < arr[right]) {
maxIndex = right;
}
if (maxIndex != index) {
swap(arr[maxIndex], arr[index]);
maxHeapify(arr, maxIndex, heapSize);
}
return;
}
template
void build(T arr[], int heapSize) {
for (int i = heapSize / 2 - 1; i >= 0; i--) {
maxHeapify(arr, i, heapSize);
}
}
template
void sort(T arr[], int heapSize) {
build(arr, heapSize);
for (int i = heapSize - 1; i > 0; i--) {
swap(arr[0], arr[i]);
maxHeapify(arr, 0, i);
}
}
template
void swap(T &a, T &b) {
T temp = a;
a = b;
b = temp;
}