Penyortiran tumpukan dibagi menjadi dua proses:
1. Bangun tumpukan.
Tumpukan pada dasarnya adalah pohon biner yang sepenuhnya dan harus memenuhi yang berikut: Kata kunci dari simpul non-daun di pohon tidak lebih besar dari (atau tidak kurang dari) kata kunci anak (jika ada) simpul.
Tumpukan dibagi menjadi: tumpukan akar besar dan tumpukan akar kecil. Urutan naik digunakan untuk mengurutkan tumpukan akar yang besar, dan urutan menurun digunakan untuk mengurutkan tumpukan akar kecil.
Jika itu adalah tumpukan akar yang besar, simpul dengan nilai terbesar disesuaikan dengan heap root dengan menyesuaikan fungsi.
2. Simpan heap root di ekor dan panggil fungsi penyesuaian untuk urutan yang tersisa. Setelah penyesuaian selesai, simpan pengikut maksimum di ekor -1 (-1, -2, ..., -i), dan kemudian sesuaikan urutan yang tersisa dan ulangi prosesnya sampai penyortiran selesai.
Salinan kode adalah sebagai berikut:
// Sesuaikan fungsinya
function headadjust (elemen, pos, len) {
// simpan nilai node saat ini
var swap = elemen [pos];
// Temukan simpul anak di sebelah kiri simpul saat ini
var anak = pos * 2 + 1;
// rekursif sampai tidak ada anak
while (anak <len) {
// Jika simpul saat ini memiliki simpul anak di sebelah kanan dan simpul anak yang tepat lebih besar, gunakan simpul anak yang tepat
// Bandingkan dengan node saat ini
if (anak + 1 <len && elemen [anak] <elemen [anak + 1]) {
anak += 1;
}
// Bandingkan simpul saat ini dengan simpul anak terbesar, jika nilainya kurang dari, lakukan pertukaran nilai, dan temukan simpul saat ini setelah pertukaran
// Di simpul anak
if (elemen [pos] <elemen [anak]) {
elemen [pos] = elemen [anak];
pos = anak;
anak = pos * 2 + 1;
}
kalau tidak{
merusak;
}
elemen [pos] = swap;
}
}
// Bangun tumpukan
fungsi buildheap (elemen) {
// Mulai dari simpul terakhir dengan node anak, bandingkan node dengan node anaknya,
// Setelah bertukar angka terbesar dengan node ini, proses pertukaran yang sama dilakukan pada simpul depan secara bergantian.
// Sampai tumpukan atas yang besar dibangun (pesanan naik adalah atasan besar, urutan menurun adalah atasan kecil)
untuk (var i = elemen.length/2; i> = 0; i-) {
headadjust (Elements, I, Elements.Length);
}
}
function sort (elemen) {
// Bangun tumpukan
buildheap (elemen);
// Sesuaikan dari ujung urutan
untuk (var i = elemen.length-1; i> 0; i-) {
// Bagian atas tumpukan selalu merupakan elemen terbesar, jadi bagian atas tumpukan dan elemen ekor akan ditukar.
// Elemen maksimum disimpan di akhir dan tidak berpartisipasi dalam penyesuaian berikutnya
var swap = elemen [i];
elemen [i] = elemen [0];
elemen [0] = swap;
// melakukan penyesuaian, sesuaikan elemen maksimum ke bagian atas heap
headadjust (elemen, 0, i);
}
}
var elemen = [3, 1, 5, 7, 2, 4, 9, 6, 10, 8];
console.log ('Sebelum:' + elemen);
urutkan (elemen);
Console.log ('After:' + Elements);
efisiensi:
Kompleksitas Waktu: Terbaik: O (NLOG2N), terburuk: O (nlog2n), rata -rata: O (nlog2n).
Kompleksitas ruang: O (1).
Stabilitas: tidak stabil