Keduanya tampak sangat mirip dan memiliki struktur yang hampir identik. Apa bedanya? Apa kompleksitas waktu untuk operasi yang berbeda
Berapa banyak tumpukan-tumpukan berbeda yang ada untuk daftar nnn bilangan bulat? Contoh: daftar [1, 2, 3, 4] Max-heap bisa berupa 4 3 2 1: 4 / \ 3 2 / 1 atau 4 2 3 1: 4 / \ 2 3
Dalam banyak diskusi tentang tumpukan biner, biasanya hanya kunci-menurun terdaftar sebagai operasi yang didukung untuk tumpukan-min. Sebagai contoh, CLR bab 6.1 dan halaman wikipedia ini . Mengapa tidak menambah kunci yang biasanya terdaftar untuk min-heap? Saya membayangkan adalah mungkin untuk...
Kemungkinan besar, pertanyaan ini diajukan sebelumnya. Ini dari masalah CLRS (2nd Ed) 6.5-8 - Berikan algoritma waktu untuk menggabungkanO(nlgk)O(nlgk)O(n \lg k)kkk diurutkan daftar menjadi satu daftar diurutkan, di mana adalah jumlah total elemen dalam semua daftar masukan. (Petunjuk: Gunakan...
Saya perlu bantuan mencari fungsi potensial untuk heap max sehingga ekstrak max selesai dalam waktu diamortisasi. Saya harus menambahkan bahwa saya tidak memiliki pemahaman yang baik tentang metode potensial.O ( 1 )HAI(1)O(1) Saya tahu bahwa fungsi penyisipan harus "membayar" lebih banyak untuk...
Tumpukan Meldable Acak memiliki operasi "berbaur", yang kemudian kita gunakan untuk mendefinisikan semua operasi lain, termasuk memasukkan. Pertanyaannya adalah, berapa tinggi yang diharapkan dari pohon itu dengan nnn node? Teorema 1 dari Gambin dan Malinkowski, Antrian Prioritas Acak yang Dapat...