kupacrendezés
HeapSort(A):
n = A mérete
BuildMaxHeap(A, n)
ciklus i = n-1-től 1-ig:
cseréljük meg A és A elemet
MaxHeapify(A, 0, i)
BuildMaxHeap(A, n):
ciklus i = n//2-1-től 0-ig:
MaxHeapify(A, i, n)
MaxHeapify(A, i, n):
left = 2*i + 1
right = 2*i + 2
largest = i
ha left < n és A > A:
largest = left
ha right < n és A > A:
largest = right
ha largest != i:
cseréljük meg A és A elemet
MaxHeapify(A, largest, n)
def heapify(arr, n, i):
largest = i # Gyökér
left = 2 * i + 1 # Bal gyermek
right = 2 * i + 2 # Jobb gyermek
# Ha a bal gyermek nagyobb, mint a gyökér
if left < n and arr > arr:
largest = left
# Ha a jobb gyermek nagyobb, mint a legnagyobb
if right < n and arr > arr:
largest = right
# Ha a legnagyobb nem a gyökér
if largest != i:
arr, arr = arr, arr # Cseréljük
heapify(arr, n, largest)
def heapsort(arr):
n = len(arr)
# Max-kupac építése
for i in range(n // 2 - 1, -1, -1):
heapify(arr, n, i)
# Elem eltávolítása a kupacból
for i in range(n - 1, 0, -1):
arr, arr = arr, arr # Gyökér és utolsó elem cseréje
heapify(arr, i, 0)
# Példa
data =
heapsort(data)
print("Rendezett tömb:", data)
Kimenet:
Rendezett tömb:
#include <iostream>
#include <vector>
using namespace std;
void heapify(vector<int>& arr, int n, int i) {
int largest = i; // Gyökér
int left = 2 * i + 1; // Bal gyermek
int right = 2 * i + 2; // Jobb gyermek
// Ha a bal gyermek nagyobb, mint a gyökér
if (left < n && arr > arr) {
largest = left;
}
// Ha a jobb gyermek nagyobb, mint a legnagyobb
if (right < n && arr > arr) {
largest = right;
}
// Ha a legnagyobb nem a gyökér
if (largest != i) {
swap(arr, arr);
heapify(arr, n, largest); // Rekurzív hívás
}
}
void heapsort(vector<int>& arr) {
int n = arr.size();
// Max-kupac építése
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(arr, n, i);
}
// Elem eltávolítása a kupacból
for (int i = n - 1; i > 0; i--) {
swap(arr, arr); // Gyökér és utolsó elem cseréje
heapify(arr, i, 0); // Kupac újraépítése
}
}
int main() {
vector<int> data = {12, 11, 13, 5, 6, 7};
heapsort(data);
cout << "Rendezett tömb: ";
for (int num : data) {
cout << num << " ";
}
cout << endl;
return 0;
}
Kimenet:
Rendezett tömb: 5 6 7 11 12 13
A kupacrendezés hatékony és megbízható módszer nagy adathalmazok rendezésére, különösen akkor, ha a memóriagazdálkodás kiemelten fontos.