Mengapa sebagian besar bahasa menyediakan min-heap, bukan implementasi max-heap?

19

Saya hanya memperhatikan sesuatu dan saya bertanya-tanya apakah ada alasan untuk itu. Kecuali untuk C ++ (std :: priority_queue adalah heap maks), saya tidak tahu bahasa lain yang menawarkan heap maks.

Modul heapq Python mengimplementasikan min-heap biner di atas daftar.

Pustaka Java berisi kelas PriorityQueue, yang mengimplementasikan antrian min-priority.

Pustaka Go berisi modul container / heap, yang mengimplementasikan min-heap di atas semua struktur data yang kompatibel.

Kerangka kerja Core Foundation Apple berisi struktur CFBinaryHeap, yang mengimplementasikan min-heap.

Saya menemukan tumpukan maksimum lebih intuitif daripada tumpukan kecil dan saya percaya secara teknis perbedaan implementasi hanya masalah mengubah operator perbandingan. Apakah ada alasan nyata? Sebagian besar aplikasi membutuhkan min, bukan max heap? Terima kasih sebelumnya

design algorithms Bernardo Pires
sumber
Bukankah mereka persis sama? Saya memilih untuk menutup sebagai argumentatif.
2
Hanya beberapa hari yang lalu saya membutuhkan min heap di C ++ dan agak kesal karena priority_queue default ke max heap. Itu memaksa saya untuk mendefinisikan operator> pada kelas kustom saya, yang sudah memiliki operator <. Saat bekerja dengan grafik, Anda biasanya ingin memprioritaskan tepi terpendek, sehingga Anda memerlukan tumpukan minimum.
LaC
2
@ LaC: bisa Anda gunakan std::not2(std::less<T>()).

Jawaban:

9

Seperti yang diamati orang lain, jika heap menerima pembanding, maka tidak terlalu sulit untuk mendapatkan satu perilaku atau yang lain. Namun, pembacaan cepat Kode Google menunjukkan bahwa min-heap jauh lebih lazim dalam kode aktual, karena dua aplikasi yang muncul berulang kali.

  • Dijkstra / A * / banyak algoritma jalur terpendek lainnya (karena jalur parsial bertambah panjang).

  • Simulasi acara (karena waktu berjalan maju).

Juga, saya berpendapat bahwa karena pengurutan default mengembalikan item kecil ke besar, maka seharusnya tumpukan default.

orang yg lambat
sumber
2
Saya biasanya memprogram dalam C ++, dan bertanya-tanya sebaliknya: mengapa C ++ tidak mengimplementasikan min-heap? Seperti yang Anda katakan, sebagian besar algoritma menggunakan min-heap.
Martín Fixman
5

Ini hanya masalah selera. Saya tidak berpikir akan ada alasan khusus. Ini seperti beberapa orang suka menyatakan masalah optimalisasi sebagai meminimalkan biaya, sementara yang lain suka mengatakan memaksimalkan keuntungan.


sumber
3

Sebagian besar bahasa yang saya tahu memungkinkan untuk melewatkan parameter untuk memutuskan apakah itu harus min- atau max-heap. Jadi nilai defaultnya agak arbitrer. Saya kira untuk sebagian besar bahasa itu adalah masalah konsistensi untuk menentukan apa operator default. Untuk C ++ di stl, defaultnya std::lessmengarah ke min-heap.

Konsistensi penggunaan std::lessuntuk default di mana-mana berarti Anda hanya perlu mengimplementasikan perbandingan ini ketika Anda menggunakan segala jenis struktur data dan Anda tidak harus memutuskan struktur data mana yang akan Anda gunakan nanti ketika Anda mendesain kelas Anda. Saya kira itu sama untuk bahasa lain dengan satu-satunya perbedaan yang lebih besar dari perbandingan adalah standar.

LiKao
sumber
3
Saya tidak berpikir ada hubungan seperti itu. Anda dapat mengimplementasikan salah satu dari tumpukan ini menggunakan <atau>. Memang, std :: less adalah default di STL, tetapi mereka mengimplementasikan heap max bukannya min heap.
LaC
1

Pada dasarnya, nilai indeks adalah angka arbitrer. Jika Anda percaya bahwa angka tersebut mewakili prioritas, dan angka yang lebih besar adalah prioritas yang lebih tinggi, maka tumpukan maksimum masuk akal. Tetapi jika angka-angka tersebut mewakili, misalnya, angka-angka toko roti konseptual ("Ambil nomor") maka min-heap lebih masuk akal.

Anda selalu dapat mengonversi dari satu ke yang lain dengan mengambil komplemen 1 dari indeks.

Daniel R Hicks
sumber