Penjelasan grafik terperinci tentang algoritma pengisihan timbunan Timbunan dan pelaksanaan kod JavaScript_Pengetahuan asas

1. Saya perlu bercakap tentang pokok binari
Untuk memahami timbunan, anda mesti terlebih dahulu memahami pokok binari Dalam sains komputer, pokok binari ialah struktur pokok di mana setiap nod mempunyai paling banyak dua subpokok. Biasanya subtree dipanggil "subtree kiri" dan "subtree kanan". Pokok binari sering digunakan untuk melaksanakan pokok carian binari dan timbunan binari.
Setiap nod pokok binari mempunyai paling banyak dua subpokok (tiada nod dengan darjah lebih daripada 2 Subpokok pokok binari dibahagikan kepada subpokok kiri dan kanan, dan susunannya tidak boleh diterbalikkan. Tahap ke-i bagi pokok binari mempunyai paling banyak 2i - 1 nod; pokok binari dengan kedalaman k mempunyai paling banyak 2k - 1 nod untuk mana-mana pokok binari T, jika bilangan nod terminal ialah n0, bilangan nod dengan darjah 2 ialah n2, maka n0 = n2 + 1.
Tiga perbezaan utama antara pokok dan pokok binari:
Bilangan nod pokok mestilah sekurang-kurangnya 1, manakala bilangan nod pokok binari boleh 0
Tiada had kepada darjah maksimum nod dalam pokok, manakala darjah maksimum nod dalam pokok binari ialah 2
Nod pokok tidak dibahagikan kepada kiri dan kanan, manakala nod pokok binari dibahagikan kepada kiri dan kanan
Pokok binari dibahagikan kepada pokok binari lengkap dan pokok binari penuh
Pokok binari penuh: Pokok dengan kedalaman k dan 2k - 1 nod dipanggil pokok binari penuh

(pokok binari penuh dengan kedalaman 3)
Pokok binari lengkap: Pokok binari dengan kedalaman k dan n nod Jika dan hanya jika setiap nodnya sepadan dengan nod bernombor 1 hingga n dalam pokok binari penuh dengan kedalaman k, ia dipanggil pokok binari lengkap

(pokok binari lengkap dengan kedalaman 3)
2. Apakah timbunan?
Timbunan (timbunan binari) boleh dianggap sebagai pokok binari yang lengkap Sifat "cemerlang" bagi pokok binari yang lengkap ialah setiap tahap kecuali tahap terendah adalah penuh, yang membolehkan timbunan menggunakan tatasusunan untuk Diwakili (biasa. pokok binari biasanya diwakili oleh senarai terpaut sebagai bekas asas), setiap nod sepadan dengan elemen dalam tatasusunan.
Seperti yang ditunjukkan di bawah, ini ialah hubungan antara timbunan dan tatasusunan

(Saling hubungan antara timbunan dan tatasusunan)
Untuk subskrip i nod tertentu, subskrip nod induk dan nod anak nod ini boleh dikira dengan mudah:
Induk(i) = lantai(i/2), subskrip nod induk i
Kiri(i) = 2i, subskrip nod anak kiri i
Kanan(i) = 2i + 1, subskrip nod anak kanan i

Timbunan binari biasanya dibahagikan kepada dua jenis: timbunan maksimum dan timbunan minimum.
Timbunan maksimum:
Nilai elemen maksimum dalam timbunan maks muncul pada nod akar (atas timbunan)
Nilai elemen setiap nod induk dalam timbunan adalah lebih besar daripada atau sama dengan nod anaknya (jika wujud)

(timbunan maksimum)
Timbunan minimum:
Nilai elemen terkecil dalam timbunan min muncul pada nod akar (bahagian atas timbunan)
Nilai elemen setiap nod induk dalam timbunan adalah kurang daripada atau sama dengan nod anaknya (jika wujud)

(timbunan min)
3. Prinsip pengisihan timbunan
Isih timbunan adalah untuk mengeluarkan nombor maksimum di bahagian atas timbunan maksimum, terus melaraskan timbunan yang tinggal kepada timbunan maksimum, dan mengeluarkan nombor maksimum di bahagian atas timbunan lagi Proses ini berterusan sehingga ke sana hanya tinggal satu nombor sahaja. Takrifkan operasi berikut pada timbunan:
Max-Heapify: Laraskan nod anak akhir timbunan supaya nod anak sentiasa lebih kecil daripada nod induk
Buat timbunan maksimum (Build-Max-Heap): Susun semula semua data dalam timbunan untuk menjadikannya timbunan maksimum
Isih Timbunan: Alih keluar nod akar data pertama dan lakukan operasi rekursif pelarasan timbunan maksimum
Sebelum meneruskan perbincangan berikut, satu perkara yang perlu diberi perhatian ialah tatasusunan semuanya Berasaskan Sifar, yang bermaksud model struktur data timbunan kami akan berubah

（Berasaskan Sifar）
Sejajar dengan itu, beberapa formula pengiraan juga mesti dilaraskan dengan sewajarnya:
Induk(i) = lantai((i-1)/2), subskrip nod induk i
Kiri(i) = 2i + 1, subskrip nod anak kiri i
Kanan(i) = 2(i + 1), subskrip nod anak kanan i
Fungsi pelarasan timbunan maksimum (MAX-HEAPIFY) adalah untuk mengekalkan sifat timbunan maksimum dan merupakan subrutin teras untuk mencipta timbunan maksimum Proses fungsi adalah seperti yang ditunjukkan dalam rajah:

(Max-Heapify)
Memandangkan selepas satu pelarasan, timbunan masih melanggar sifat timbunan, ujian rekursif diperlukan untuk menjadikan keseluruhan timbunan memenuhi sifat timbunan Ini boleh dinyatakan dalam JavaScript seperti berikut:

/**
 * 从 index 开始检查并保持最大堆性质
 *
 * @array
 *
 * @index 检查的起始下标
 *
 * @heapSize 堆大小
 *
 **/
function maxHeapify(array, index, heapSize) {
 var iMax = index,
   iLeft = 2 * index + 1,
   iRight = 2 * (index + 1);

 if (iLeft < heapSize && array[index] < array[iLeft]) {
  iMax = iLeft;
 }

 if (iRight < heapSize && array[iMax] < array[iRight]) {
  iMax = iRight;
 }

 if (iMax != index) {
  swap(array, iMax, index);
  maxHeapify(array, iMax, heapSize); // 递归调整
 }
}

function swap(array, i, j) {
 var temp = array[i];
 array[i] = array[j];
 array[j] = temp;
}

Secara umumnya, rekursi digunakan terutamanya dalam kaedah bahagi dan takluk, tetapi bahagi dan takluk tidak diperlukan di sini. Selain itu, panggilan rekursif memerlukan menolak/mengosongkan timbunan, yang mempunyai sedikit kelemahan prestasi berbanding dengan lelaran. Sudah tentu, mengikut peraturan 20/80, ini boleh diabaikan. Tetapi jika anda merasakan bahawa menggunakan rekursi akan membuat anda berasa tidak selesa, anda juga boleh menggunakan lelaran, seperti berikut:

/**
 * 从 index 开始检查并保持最大堆性质
 *
 * @array
 *
 * @index 检查的起始下标
 *
 * @heapSize 堆大小
 *
 **/
function maxHeapify(array, index, heapSize) {
 var iMax, iLeft, iRight;
 while (true) {
  iMax = index;
  iLeft = 2 * index + 1;
  iRight = 2 * (index + 1);
  if (iLeft < heapSize && array[index] < array[iLeft]) {
   iMax = iLeft;
  }

  if (iRight < heapSize && array[iMax] < array[iRight]) {
   iMax = iRight;
  }

  if (iMax != index) {
   swap(array, iMax, index);
   index = iMax;
  } else {
   break;
  }
 }
}

function swap(array, i, j) {
 var temp = array[i];
 array[i] = array[j];
 array[j] = temp;
}

Fungsi mencipta timbunan maksimum (Build-Max-Heap) adalah untuk mengubah tatasusunan menjadi timbunan maksimum. Ia menerima dua parameter: susunan dan saiz timbunan akan memanggil Max-Heapify atas. Ubah tatasusunan dan buat timbunan maksimum. Oleh kerana Max-Heapify boleh memastikan bahawa nod selepas nod dengan subskrip i memenuhi sifat timbunan maksimum, panggilan bawah ke atas Max-Heapify boleh mengekalkan sifat ini semasa proses transformasi. Jika bilangan elemen dalam timbunan maksimum ialah n, maka Build-Max-Heap bermula dari Parent(n) dan memanggil Max-Heapify dalam urutan. Prosesnya adalah seperti berikut:

Diterangkan dalam JavaScript seperti berikut:

function buildMaxHeap(array, heapSize) {
 var i,
   iParent = Math.floor((heapSize - 1) / 2);
   
 for (i = iParent; i >= 0; i--) {
  maxHeapify(array, i, heapSize);
 }
}

Isih Timbunan ialah algoritma antara muka isihan Timbunan terlebih dahulu memanggil Build-Max-Heap untuk mengubah tatasusunan menjadi timbunan maksimum, kemudian menukar elemen atas dan bawah timbunan, kemudian menaikkan bahagian bawah, dan akhirnya Recall Max-Heapify untuk mengekalkan sifat timbunan maksimum. Memandangkan elemen atas timbunan mestilah elemen terbesar dalam timbunan, selepas satu operasi, unsur terbesar yang wujud dalam timbunan dipisahkan daripada timbunan Selepas mengulangi n-1 kali, tatasusunan disusun. Seluruh proses adalah seperti berikut:

Diterangkan dalam JavaScript seperti berikut:

function heapSort(array, heapSize) {

 buildMaxHeap(array, heapSize);

 for (int i = heapSize - 1; i > 0; i--) {
  swap(array, 0, i);
  maxHeapify(array, 0, i);
 } 
}

4.Pelaksanaan bahasa JavaScript
Akhir sekali, susun perkara di atas ke dalam kod javascript lengkap seperti berikut:

function heapSort(array) {

 function swap(array, i, j) {
  var temp = array[i];
  array[i] = array[j];
  array[j] = temp;
 }

 function maxHeapify(array, index, heapSize) {
  var iMax,
   iLeft,
   iRight;
  while (true) {
   iMax = index;
   iLeft = 2 * index + 1;
   iRight = 2 * (index + 1);

   if (iLeft < heapSize && array[index] < array[iLeft]) {
    iMax = iLeft;
   }

   if (iRight < heapSize && array[iMax] < array[iRight]) {
    iMax = iRight;
   }

   if (iMax != index) {
    swap(array, iMax, index);
    index = iMax;
   } else {
    break;
   }
  }
 }

 function buildMaxHeap(array) {
  var i,
   iParent = Math.floor(array.length / 2) - 1;

  for (i = iParent; i >= 0; i--) {
   maxHeapify(array, i, array.length);
  }
 }

 function sort(array) {
  buildMaxHeap(array);

  for (var i = array.length - 1; i > 0; i--) {
   swap(array, 0, i);
   maxHeapify(array, 0, i);
  }
  return array;
 }

 return sort(array);
}

5. Aplikasi algoritma isihan timbunan

(1) Prestasi/kerumitan algoritma
Kerumitan masa bagi jenis timbunan adalah sangat stabil (kita dapat melihat bahawa ia tidak sensitif kepada data input), ia adalah kerumitan O(n㏒n), dan kes terbaik adalah sama dengan kes terburuk.
Walau bagaimanapun, kerumitan ruangnya berbeza dari pelaksanaan ke pelaksanaan. Dua kerumitan biasa telah dibincangkan di atas: O(n) dan O(1). Selaras dengan prinsip penjimatan ruang, saya mengesyorkan kaedah kerumitan O(1).

(2) Kestabilan algoritma
Isihan timbunan melibatkan sebilangan besar proses penyaringan dan pergerakan serta merupakan algoritma pengisihan yang tidak stabil.

(3) Algoritma senario terpakai
Isih timbunan akan menyebabkan overhed yang agak besar dalam proses penubuhan dan pelarasan timbunan, dan tidak sesuai apabila terdapat sedikit elemen. Walau bagaimanapun, ia masih merupakan pilihan yang baik apabila terdapat banyak elemen. Terutama apabila menyelesaikan masalah seperti "nombor pertama n terbesar", ia hampir menjadi algoritma pilihan.