Kami terus membenamkan diri dalam berbagai tumpukan.Hari ini kami akan menganalisis metode pemesanan yang elegan yang menggunakan tumpukan khusus berdasarkan nomor Leonardo.Banyak yang telah mendengar tentang penyortiran ini, tetapi hanya sedikit orang yang tahu persis cara kerjanya. Hari ini kita akan melihat bahwa tidak ada yang rumit di dalamnya. Metode ini ditemukan oleh Edsger Dijkstra yang legendaris. Selain banyak pencapaian paling cemerlang dalam teori algoritma, ia juga merupakan penulis pernyataan yang sangat lucu: “Siswa yang sebelumnya belajar Dasar, hampir tidak mungkin untuk mengajar pemrograman yang baik. Sebagai programmer potensial, mereka telah mengalami degradasi mental yang tidak dapat dipulihkan. ”
Saya harap bukan penghujatan bahwa animasi dalam artikel dibuat menggunakan VBA :-)
EDISON.
, Android iOS.
! ;-)
Heap sorting itu sendiri sangat baik, karena kompleksitas waktunya adalah O ( n log n ) terlepas dari data. Agar tidak menjadi array, kompleksitas heapsort tidak pernah menurun ke O ( n 2 ) , yang dapat terjadi, misalnya, dengan penyortiran cepat. Sisi lain dari koin adalah bahwa penyortiran berdasarkan tumpukan biner tidak dapat dipercepat, O ( n ) kompleksitas juga tidak dapat diharapkan (tetapi penyortiran cepat yang sama, dalam kondisi tertentu, dapat mencapai indikator tersebut).Secara umum, ada pertanyaan dalam agenda: apakah mungkin untuk merancang sehingga kompleksitas waktu menyortir berdasarkan tumpukan, di satu sisi, tidak lebih rendah dariO ( n log n ) , tetapi dalam skenario yang menguntungkan (khususnya, jika array yang hampir diurutkan diproses) meningkat menjadi O ( n ) ?Masalah ini secara pribadi ditangani oleh Edsger Dijkstra sendiri, yang menemukan bahwa ya, itu mungkin.Diasumsikan bahwa mereka yang membaca artikel ini memahami bagaimana penyortiran berdasarkan tumpukan bekerja secara umum, mereka tahu apa itu penyortiran pohon dan mengapa penyaringan diperlukan. Jika seseorang memiliki kesenjangan dalam pengetahuan ini, maka sebelum melanjutkan membaca, saya sarankan Anda membaca artikel sebelumnya .Apa yang salah dengan tumpukan biner?
Mari kita lihat bagaimana heapsort mengurutkan array yang hampir teratur dan melihat mengapa algoritma ini tidak memproses data yang masuk lebih cepat.Klik pada animasi untuk pergi ke artikel “Menyortir berdasarkan n-piramida.”Hal pertama yang menarik perhatian Anda adalah ketika menyaring, maxima terus-menerus didorong ke akar tumpukan, yang sesuai dengan elemen pertama array. Jika array input hampir dipesan, maka untuk algoritme ini hanya akan menambah sedikit kerja. Elemen yang lebih kecil akan tetap pertama turun pohon, yaitu bergerak lebih dekat ke ujung array, bukan ke awal.Faktor perlambatan kedua, yang tidak begitu jelas, adalah tumpukan biner standar itu sendiri selalu pohon seimbang. Dalam kasus data yang awalnya dipesan, ini memainkan peran negatif. Jika ada data acak dalam array asli, maka mereka didistribusikan secara merata di pohon seimbang, dan beberapa memilah melewati semua cabang kira-kira jumlah yang sama kali. Untuk data yang hampir dipesan, pohon yang tidak seimbang lebih disukai - dalam hal ini, data pada bagian array yang sesuai dengan cabang-cabang pohon yang lebih panjang akan diproses lebih jarang daripada yang lain.Angka Leonardo
Untuk mengatasi kedua masalah, Dijkstra mengusulkan menggunakan tumpukan biner khusus berdasarkan nomor Leonardo.Angka Leonardo hampir seperti angka Fibonacci, tetapi hanya lebih baik.Serangkaian bilangan Leonardo diberikan secara rekursif:L 0 = 1L 1 = 1L n = L n - 1 + L n - 2 + 120 angka Leonardo pertama:1, 1, 3, 5, 9, 15, 25, 41, 67 , 109, 177, 287, 465, 753, 1219, 1973, 3193, 5167, 8361, 13529Benar-benar bilangan bulat mana pun dapat direpresentasikan sebagai jumlah bilangan Leonardo yang memiliki nomor seri berbeda.Ini sangat berguna dalam kasus kami. Array nelemen tidak selalu dapat direpresentasikan sebagai satu tumpukan Leonardo (jika n bukan angka Leonardo). Tetapi kemudian, array apa pun selalu dapat dibagi menjadi beberapa subarrays yang akan sesuai dengan nomor Leonardo yang berbeda, yaitu menjadi tumpukan dari urutan yang berbeda.Berikut adalah contoh array elemen ke-21, yang terdiri dari tiga tumpukan Leonard. Di setiap tumpukan, jumlah node sesuai dengan sejumlah Leonardo.Poin penting yang perlu diketahui:- Setiap tumpukan Leonardov adalah pohon biner yang tidak seimbang.
- Akar setiap heap adalah elemen terakhir (dan bukan yang pertama, seperti pada heap biner biasa) dari subarray yang sesuai.
- Setiap simpul dengan semua turunannya juga merupakan tumpukan Leonard dengan urutan yang lebih kecil.
Bangun dan bongkar tumpukan
Dalam rumus perulangan untuk bilangan Leonardo,L n = L n - 1 + L n - 2 + 1sangat senang dengan unit di akhir.Dan itulah kenapa. Misalkan kita memiliki dua subarrays yang berdekatan dalam array yang sesuai dengan tumpukan yang dibangun pada dua bilangan Leonardo yang berdekatan. Menggunakan elemen segera setelah subarrays ini, subarrays ini dapat digabungkan menjadi tumpukan umum, yang sesuai dengan nomor Leonard berikutnya.Melalui elemen-elemen dalam array, kami membangun banyak tumpukan Leonard. Jika menggunakan elemen Anda dapat menggabungkan dua tumpukan sebelumnya (ini dimungkinkan jika dan hanya jika dua tumpukan sebelumnya sesuai dengan dua angka Leonardo berturut-turut), lalu gabungkan. Jika menggabungkan tidak mungkin (dua tumpukan sebelumnya tidak sesuai dengan dua angka Leonardo berturut-turut), maka elemen saat ini hanya membentuk tumpukan baru dari satu elemen yang sesuai dengan yang pertama (atau kedua, jika yang pertama digunakan sebelumnya) nomor Leonardo.Pada tahap kedua algoritma, proses sebaliknya terjadi - kami mengurai tumpukan. Jika kita menghapus root di heap, maka kita mendapatkan dua heap yang lebih kecil sesuai dengan dua angka Leonardo sebelumnya. Ini dapat dilakukan karena:L n - 1 = L n - 1+ L n - 2Dalam bilangan Fibonacci tidak ada unit yang berguna, oleh karena itu kami tidak menggunakan tumpukan Fibonacci.Sortir Halus :: Smoothsort
Algoritma terakhir:- I. Buat sekelompok tumpukan Leonard dari array, yang masing-masing adalah pohon penyortiran.
- I.1. Iterasi elemen-elemen array dari kiri ke kanan.
- II.1. Kami memeriksa apakah menggunakan elemen saat ini adalah mungkin untuk menggabungkan dua tumpukan paling kiri di tumpukan Leonard yang ada:
- II.1.a. Jika ya, maka kami menggabungkan dua tumpukan paling kiri menjadi satu, elemen saat ini menjadi akar tumpukan ini, kami menyaring tumpukan gabungan.
- II.1.b. Jika tidak, tambahkan elemen saat ini sebagai tumpukan baru (terdiri dari satu simpul sejauh ini) ke tumpukan yang ada dari tumpukan Leonard.
- II. , :
- II.1. . , .
- II.2. ( ) ( ).
- II.3. , . .
- II.4. ( ), .
- II.5. Setelah memindahkan elemen maksimum ke ujung, bagian array yang diurutkan meningkat, dan bagian yang tidak disortir berkurang. Ulangi langkah II.1-II.4 untuk bagian array yang belum disortir.
Contoh implementasi python
import random
def smoothsort(lst):
leo_nums = leonardo_numbers(len(lst))
heap = []
for i in range(len(lst)):
if len(heap) >= 2 and heap[-2] == heap[-1] + 1:
heap.pop()
heap[-1] += 1
else:
if len(heap) >= 1 and heap[-1] == 1:
heap.append(0)
else:
heap.append(1)
restore_heap(lst, i, heap, leo_nums)
for i in reversed(range(len(lst))):
if heap[-1] < 2:
heap.pop()
else:
k = heap.pop()
t_r, k_r, t_l, k_l = get_child_trees(i, k, leo_nums)
heap.append(k_l)
restore_heap(lst, t_l, heap, leo_nums)
heap.append(k_r)
restore_heap(lst, t_r, heap, leo_nums)
def leonardo_numbers(hi):
a, b = 1, 1
numbers = []
while a <= hi:
numbers.append(a)
a, b = b, a + b + 1
return numbers
def restore_heap(lst, i, heap, leo_nums):
current = len(heap) - 1
k = heap[current]
while current > 0:
j = i - leo_nums[k]
if (lst[j] > lst[i] and
(k < 2 or lst[j] > lst[i-1] and lst[j] > lst[i-2])):
lst[i], lst[j] = lst[j], lst[i]
i = j
current -= 1
k = heap[current]
else:
break
while k >= 2:
t_r, k_r, t_l, k_l = get_child_trees(i, k, leo_nums)
if lst[i] < lst[t_r] or lst[i] < lst[t_l]:
if lst[t_r] > lst[t_l]:
lst[i], lst[t_r] = lst[t_r], lst[i]
i, k = t_r, k_r
else:
lst[i], lst[t_l] = lst[t_l], lst[i]
i, k = t_l, k_l
else:
break
def get_child_trees(i, k, leo_nums):
t_r, k_r = i - 1, k - 2
t_l, k_l = t_r - leo_nums[k_r], k - 1
return t_r, k_r, t_l, k_l
def main(n):
lst = list(range(n))
random.shuffle(lst)
print(lst)
smoothsort(lst)
print(lst)
Kompleksitas waktu
Jika kita mengambil array yang hampir dipesan sebagai input, maka visualisasi menunjukkan mengapa array tersebut diproses lebih cepat.Penghematan hanya terjadi karena penyaringan. Dalam data yang hampir dipesan, saringan tenggelam dangkal di pohon, termasuk setelah tumpukan secara bertahap dibubarkan di tahap kedua. Dalam data awalnya acak, pengayakan lebih mahal, karena sering kali jatuh ke level terakhir.Mari kita perkirakan kompleksitas waktu total.Pada tahap pertama, kita beralih pada n elemen, menambahkannya ke tumpukan yang sudah ada di sebelah kiri. Menambahkan ke heap itu sendiri dilewati di O (1), tetapi kemudian untuk heap Anda perlu membuat ayak. Dalam data yang dipesan, pengayakan dangkal sering kali menghabiskan biaya O (1) untuk satu elemen yang ditambahkan ke heap. Dalam data yang tidak berurutan, pengayakan untuk setiap penambahan dihitung biayanya dalam O (log n ), karena sebagai akibat dari keacakan, pengayakan harus melalui tingkat pohon sering ke bagian paling bawah.Oleh karena itu, pada tahap pertama, kompleksitas waktu terbaik adalah:untuk data yang hampir dipesan - O ( n ),untuk data acak - O ( n log n ).Untuk tahap kedua, situasinya mirip. Saat bertukar maksimum berikutnya, Anda lagi perlu menyaring tumpukan di root itu. Dan metrik penyaringan untuk data yang dipesan dan tidak teratur akan berbeda.Pada tahap kedua, kompleksitas waktu terbaik sama dengan pada tahap pertama:untuk data yang hampir dipesan - O ( n ),untuk data acak - O ( n log n ).Menambahkan kompleksitas waktu untuk tahap pertama dan kedua:untuk data yang hampir dipesan - O (2 n ) = O ( n ),untuk data acak - O (2 n log n ) = O ( n log n ).Secara umum, kompleksitas waktu terburuk dan rata-rata untuk pemilahan halus adalah O ( n log n ).Dijkstra dalam perhitungannya (yang tidak akan membuat saya bosan dengan Anda) membuktikan bahwa kompleksitas terbaik dengan lancar cenderung ke O ( n ) daripada data yang masuk lebih teratur. Oleh karena itu nama - pemilahan halus.Kompleksitas memori ekstra
Untuk menguraikan data menjadi banyak tumpukan Leonard, Anda hanya perlu mengingat persis angka Leonardo mana yang terlibat di setiap langkah. Mengetahui angka-angka ini, tumpukan itu sendiri disejajarkan secara algoritmik. Seri angka ini tumbuh sangat cepat, sehingga bahkan untuk array besar Anda akan memerlukan satu set angka Leonard yang sangat kecil.Binomial heap sort :: Binomial heap sort
Ada struktur pohon, sangat mirip dengan yang kami susun - tumpukan binomial . Ini juga banyak tumpukan ukuran yang berbeda, di mana masing-masing jumlah node adalah kekuatan dua. Setiap array dari sejumlah elemen dapat diperluas ke tumpukan ini, karena setiap bilangan alami didekomposisi menjadi jumlah dua-dua derajat yang berbeda.Pada prinsipnya, Anda dapat melakukan pemilahan berdasarkan binomial:Apakah ini akan bekerja lebih cepat? Hampir tidak. Tumpukan binomial bukan biner, dan dalam artikel terakhir kami menemukan bahwa meningkatkan jumlah keturunan tidak mempercepat, tetapi memperlambat layar . Selain itu, Anda dapat melihat bahwa tumpukan binomial memiliki cabang yang lebih panjang, itulah sebabnya daerah-daerah tetangga yang tertata dari array akan sedikit lebih lambat untuk terhubung satu sama lain.Tidak diketahui apakah tumpukan binomial Dijkstra secara umum dianggap sebagai dasar yang mungkin untuk algoritmanya. Namun, tumpukan Leonardov mungkin lebih optimal.Trailer Seri Berikutnya
Namun, bahkan jika tumpukan binomial bukan pilihan terbaik untuk pemilahan yang halus, Anda tidak harus membuangnya sepenuhnya.Jika pohon binomial sedikit dimodifikasi dan ide yang sangat berbeda (sangat tebal) digunakan untuk mengitarinya, kita mendapatkan algoritma asli dan efektif yang memiliki kelebihannya sendiri. Apa yang akan kita bicarakan lain kali?Klik pada animasi untuk pergi ke artikel dengan penyortiran berikutnya dengan tumpukan.Referensi
Smooth / Menghaluskan Leonardo Nomor , Binomial Heap / binomial tumpukanArtikel Seri:
Penyortiran halus hari ini telah ditambahkan ke aplikasi AlgoLab. Serta bonus - dan menyortir dengan tumpukan binomial. Jadi siapa yang ingin secara pribadi menggerakkan data di heap heaps - perbarui file excel dengan macro.