Menerapkan antrian prioritas menggunakan max heap vs BST seimbang
Balanced BST dan max heap keduanya melakukan penyisipan dan penghapusan O(logn). Namun, menemukan nilai maks dalam heap maks adalah O(1)tetapi ini O(logn)dalam BST yang seimbang.
Jika kita menghapus nilai maks dalam heap maks yang diperlukan O(logn)karena ini adalah operasi penghapusan.
Dalam BST yang seimbang, menghapus elemen maks = menemukan nilai maks + hapus; itu sama dengan logn + logn berkurang menjadi O(logn). Jadi, bahkan menghapus nilai maksimal dalam BST seimbang adalah O(logn).
Saya telah membaca salah satu aplikasi tumpukan maks adalah antrian prioritas dan tujuan utamanya adalah untuk menghapus nilai maks untuk setiap operasi dequeue. Jika menghapus elemen maks O(logn)untuk tumpukan maks dan BST seimbang, saya memiliki pertanyaan berikut
Apa tujuan dari tumpukan maksimum dalam antrian prioritas hanya karena mudah diimplementasikan daripada menggunakan BST seimbang yang dapat dicari secara penuh?
Karena tidak ada perhitungan faktor penyeimbang, tumpukan maksimum dapat disebut pohon biner tidak seimbang?
Setiap BST yang seimbang dapat digunakan sebagai antrian prioritas dan yang juga dapat dicari di
O(logn)betapapun max heap searchO(n)benar?
Semua kerumitan waktu dihitung untuk kasus terburuk. Bantuan apa pun sangat dihargai.
Jawaban
Apa tujuan dari tumpukan maksimum dalam antrian prioritas hanya karena mudah diimplementasikan daripada menggunakan BST seimbang yang dapat dicari secara penuh?
Beberapa keuntungan dari heap adalah:
Mengingat array masukan disortir, sebuah tumpukan masih bisa dibangun di O (n) waktu , sementara BST membutuhkan O (nlogn) waktu .
Jika masukan awal adalah larik, larik yang sama tersebut dapat berfungsi sebagai heap, yang berarti tidak diperlukan memori tambahan untuk itu. Meskipun seseorang dapat memikirkan cara untuk membuat BST menggunakan data yang ada di dalam array, itu akan menjadi sangat aneh (untuk tipe primitif) dan memberikan lebih banyak overhead pemrosesan. BST biasanya dibuat dari awal, menyalin data ke node saat dibuat.
Fakta menarik: array yang diurutkan juga merupakan heap, jadi jika diketahui bahwa input telah diurutkan, tidak ada yang perlu dilakukan untuk membangun heap.
Heap dapat disimpan sebagai array tanpa perlu menyimpan referensi silang , sedangkan BST biasanya terdiri dari node dengan referensi kiri & kanan. Ini setidaknya memiliki dua konsekuensi:
- Memori yang digunakan untuk BST sekitar 3 kali lebih besar dari pada heap.
- Meskipun beberapa operasi memiliki kompleksitas waktu yang sama untuk heap dan BST, overhead untuk mengadaptasi BST jauh lebih besar, sehingga waktu aktual yang dihabiskan untuk operasi ini adalah faktor (konstan) yang lebih besar dalam kasus BST.
Karena tidak ada perhitungan faktor penyeimbang, tumpukan maksimum dapat disebut pohon biner tidak seimbang?
Tumpukan sebenarnya adalah pohon biner lengkap , sehingga selalu seimbang: daun akan selalu ditempatkan di tingkat terakhir atau satu-tetapi-terakhir. BST yang menyeimbangkan diri (seperti AVL, merah-hitam, ...) tidak dapat mengalahkan penyeimbangan tingkat tinggi itu, di mana Anda akan sering memiliki daun yang muncul di tiga tingkat atau bahkan lebih.
Setiap BST yang seimbang dapat digunakan sebagai antrian prioritas dan yang juga dapat dicari di O (logn) namun pencarian heap maks adalah O (n) benar?
Ya, ini benar. Jadi jika aplikasi membutuhkan fitur pencarian, maka BST lebih unggul.
Apa tujuan dari tumpukan maksimum dalam antrian prioritas hanya karena mudah diimplementasikan daripada menggunakan BST seimbang yang dapat dicari secara penuh?
Nggak. Heap maks lebih cocok, karena diinstrumentasi dengan hati-hati untuk mengembalikan elemen berikutnya (menghormati prioritas) secepatnya, dalam waktu O (1). Itulah yang Anda inginkan dari antrian prioritas yang sesederhana mungkin.
Karena tidak ada perhitungan faktor penyeimbang, tumpukan maksimum dapat disebut pohon biner tidak seimbang?
Nggak. Ada keseimbangan juga. Singkat cerita, menyeimbangkan tumpukan dilakukan dengan operasi shift-up atau shift-down (menukar elemen yang rusak).
Setiap BST yang seimbang dapat digunakan sebagai antrian prioritas dan yang juga dapat dicari di O (logn) namun pencarian heap maks adalah O (n) benar?
Ya! Serta daftar tertaut dapat digunakan atau array. Ini hanya akan menjadi lebih mahal dalam hal notasi-O dan jauh lebih lambat dalam praktiknya.