Heap vs Binary Search Tree (BST)

Apa perbedaan antara heap dan BST?

Kapan menggunakan heap dan kapan menggunakan BST?

Jika Anda ingin mendapatkan elemen dalam mode yang diurutkan, apakah BST lebih baik daripada tumpukan?

Ringkasan

          Type      BST (*)   Heap
Insert    average   log(n)    1
Insert    worst     log(n)    log(n) or n (***)
Find any  worst     log(n)    n
Find max  worst     1 (**)    1
Create    worst     n log(n)  n
Delete    worst     log(n)    log(n)

Semua waktu rata-rata di tabel ini sama dengan waktu terburuknya kecuali untuk Sisipan.

• *: di mana-mana dalam jawaban ini, BST == BST Seimbang, karena tidak seimbang menyebalkan tanpa gejala
• **: menggunakan modifikasi sepele yang dijelaskan dalam jawaban ini
• ***: log(n)untuk tumpukan pohon penunjuk, nuntuk tumpukan array dinamis

Keuntungan tumpukan biner dibandingkan BST

• penyisipan waktu rata-rata ke dalam tumpukan biner adalah O(1), untuk BST adalah O(log(n)). Ini adalah fitur pembunuh tumpukan.

  Ada juga tumpukan lain yang mencapai O(1)amortisasi (lebih kuat) seperti Fibonacci Heap , dan bahkan kasus terburuk, seperti antrian Brodal , meskipun mungkin tidak praktis karena kinerja non-asimtotik: Apakah tumpukan Fibonacci atau antrian Brodal digunakan dalam praktik di mana saja?

• tumpukan biner dapat diimplementasikan secara efisien di atas array dinamis atau pohon berbasis pointer, hanya pohon berbasis pointer BST. Jadi untuk heap kita dapat memilih implementasi array yang lebih efisien ruang, jika kita dapat sesekali mengubah ukuran latensi.

• penciptaan tumpukan biner adalah O(n)kasus terburuk , O(n log(n))untuk BST.

Keuntungan BST dibandingkan tumpukan biner

• mencari elemen sewenang-wenang adalah O(log(n)). Ini adalah fitur pembunuh BST.

  Untuk heap, secara O(n)umum, kecuali untuk elemen terbesar yaitu O(1).

"Salah" keuntungan dari tumpukan lebih dari BST

• heap adalah O(1)menemukan max, BST O(log(n)).

  Ini adalah kesalahpahaman umum, karena sepele untuk memodifikasi BST untuk melacak elemen terbesar, dan memutakhirkannya setiap kali elemen itu dapat diubah: pada penyisipan swap yang lebih besar, pada penghapusan cari yang terbesar kedua. Bisakah kita menggunakan pohon pencarian biner untuk mensimulasikan operasi heap? (disebutkan oleh Yeo ).

  Sebenarnya, ini adalah batasan tumpukan dibandingkan dengan BST: satu - satunya pencarian yang efisien adalah untuk elemen terbesar.

Masukkan tumpukan biner rata-rata adalah O(1)

Sumber:

• Paper: http://i.stanford.edu/pub/cstr/reports/cs/tr/74/460/CS-TR-74-460.pdf
• Slide WSU: http://www.eecs.wsu.edu/~holder/courses/CptS223/spr09/slides/heaps.pdf

Argumen intuitif:

• tingkat pohon bawah memiliki elemen lebih banyak daripada tingkat atas secara eksponensial, sehingga elemen baru hampir pasti akan berada di bagian bawah
• penyisipan heap dimulai dari bawah , BST harus dimulai dari atas

Dalam tumpukan biner, meningkatkan nilai pada indeks yang diberikan juga O(1)karena alasan yang sama. Tetapi jika Anda ingin melakukan itu, ada kemungkinan bahwa Anda ingin menjaga agar indeks tambahan tetap up-to-date pada operasi heap. Bagaimana menerapkan operasi kunci-O (logn) untuk Antrian Prioritas berdasarkan min-heap? misalnya untuk Dijkstra. Mungkin tanpa biaya waktu tambahan.

GCC C ++ standar memasukkan patokan perpustakaan pada perangkat keras nyata

Saya melakukan benchmark pada sisipan C ++ std::set( Red-black tree BST ) dan std::priority_queue( dynamic array heap ) untuk melihat apakah saya benar tentang waktu insert, dan inilah yang saya dapatkan:

• kode tolok ukur
• skrip plot
• plot data
• diuji pada Ubuntu 19.04, GCC 8.3.0 di laptop Lenovo ThinkPad P51 dengan CPU: CPU Intel Core i7-7820HQ (4 core / 8 thread, basis 2.90 GHz, 8 MB cache), RAM: 2x Samsung M471A2K43BB1-CRC (2x 16GiB , 2400 Mbps), SSD: Samsung MZVLB512HAJQ-000L7 (512GB, 3.000 MB / s)

Sangat jelas:

• heap insert time pada dasarnya konstan.

  Kita dapat dengan jelas melihat titik ukuran array dinamis. Karena kami rata-rata setiap 10k menyisipkan untuk dapat melihat apa pun di atas kebisingan sistem , puncak-puncak itu sebenarnya sekitar 10k kali lebih besar daripada yang ditampilkan!

  Grafik yang diperbesar pada dasarnya mengecualikan hanya titik ukuran array, dan menunjukkan bahwa hampir semua sisipan berada di bawah 25 nanodetik.

• BST adalah logaritmik. Semua sisipan jauh lebih lambat daripada rata-rata tumpukan insert.

• Analisis rinci BST vs hashmap di: Struktur data apa yang ada di dalam std :: map di C ++?

GCC C ++ standar memasukkan patokan pustaka pada gem5

gem5 adalah simulator sistem lengkap, dan karenanya menyediakan jam yang sangat akurat m5 dumpstats. Jadi saya mencoba menggunakannya untuk memperkirakan waktu untuk setiap sisipan.

Penafsiran:

• heap masih konstan, tetapi sekarang kita melihat lebih detail bahwa ada beberapa baris, dan setiap baris yang lebih tinggi lebih jarang.

  Ini harus sesuai dengan latensi akses memori dilakukan untuk menyisipkan lebih tinggi dan lebih tinggi.

• TODO Saya benar-benar tidak dapat menafsirkan BST sepenuhnya karena tidak terlihat begitu logaritmik dan agak lebih konstan.

  Namun, dengan detail yang lebih besar ini, kita juga dapat melihat beberapa garis yang berbeda, tetapi saya tidak yakin apa yang diwakilinya: Saya berharap garis bawahnya menjadi lebih tipis, karena kita memasukkan bagian bawah atas?

Benchmarked dengan pengaturan Buildroot ini pada CPU HPI aarch64 .

BST tidak dapat diimplementasikan secara efisien pada array

Operasi tumpukan hanya perlu menggelembung ke atas atau ke bawah cabang pohon tunggal, sehingga O(log(n))kasus terburuk bertukar, O(1)rata-rata.

Menjaga BST seimbang membutuhkan rotasi pohon, yang dapat mengubah elemen atas untuk elemen lainnya, dan akan membutuhkan pemindahan seluruh larik ( O(n)).

Tumpukan dapat diimplementasikan secara efisien pada array

Indeks induk dan anak-anak dapat dihitung dari indeks saat ini seperti yang ditunjukkan di sini .

Tidak ada operasi penyeimbangan seperti BST.

Hapus min adalah operasi yang paling mengkhawatirkan karena harus dari atas ke bawah. Tapi itu selalu bisa dilakukan dengan "meresap" satu cabang tumpukan seperti yang dijelaskan di sini . Ini mengarah ke kasus terburuk O (log (n)), karena heap selalu seimbang.

Jika Anda memasukkan satu simpul untuk setiap simpul yang Anda hapus, maka Anda kehilangan keuntungan dari rata-rata sisipan O (1) asimptotik yang diberikan tumpukan karena penghapusan akan mendominasi, dan Anda sebaiknya menggunakan BST. Namun Dijkstra memperbarui node beberapa kali untuk setiap penghapusan, jadi kami baik-baik saja.

Tumpukan array dinamis vs tumpukan pohon penumpukan

Tumpukan dapat diimplementasikan secara efisien di atas tumpukan pointer: Apakah mungkin untuk membuat implementasi tumpukan biner berbasis pointer yang efisien?

Implementasi array dinamis lebih hemat ruang. Misalkan setiap elemen tumpukan hanya berisi pointer ke struct:

• implementasi pohon harus menyimpan tiga pointer untuk setiap elemen: orang tua, anak kiri dan anak kanan. Jadi penggunaan memori selalu 4n(3 pointer pohon + 1 structpointer).

  Tree BST juga akan membutuhkan informasi penyeimbangan lebih lanjut, mis. Merah-hitam.

• implementasi array dinamis dapat berukuran 2nsetelah penggandaan. Jadi rata-rata akan seperti itu 1.5n.

Di sisi lain, tumpukan pohon memiliki insert terburuk terburuk, karena menyalin array dinamis dukungan untuk menggandakan ukurannya mengambil O(n)terburuk, sedangkan tumpukan pohon hanya melakukan alokasi kecil baru untuk setiap node.

Namun, penggandaan susunan backing O(1)diamortisasi, sehingga menjadi pertimbangan latensi maksimum. Disebutkan di sini .

Filsafat

• BST menjaga properti global antara orang tua dan semua keturunan (kiri lebih kecil, kanan lebih besar).

  Node atas BST adalah elemen tengah, yang membutuhkan pengetahuan global untuk mempertahankan (mengetahui berapa banyak elemen yang lebih kecil dan lebih besar di sana).

  Properti global ini lebih mahal untuk dirawat (log n insert), tetapi memberikan pencarian yang lebih kuat (log n search).

• Tumpukan mempertahankan properti lokal antara orang tua dan anak-anak langsung (orang tua> anak-anak).

  Node atas tumpukan adalah elemen besar, yang hanya membutuhkan pengetahuan lokal untuk mempertahankan (mengetahui orang tua Anda).

Membandingkan BST vs Heap vs Hashmap:

• BST: bisa masuk akal:

  • set unordered (struktur yang menentukan apakah suatu elemen sebelumnya dimasukkan atau tidak). Tetapi hashmap cenderung lebih baik karena O (1) sisipan diamortisasi.
  • mesin sortasi. Tetapi heap pada umumnya lebih baik, itulah sebabnya heapsort jauh lebih dikenal daripada jenis pohon

• heap: hanyalah mesin sortasi. Tidak dapat menjadi set unordered yang efisien, karena Anda hanya dapat memeriksa elemen terkecil / terbesar dengan cepat.

• peta hash: hanya bisa berupa perangkat yang tidak berurutan, bukan mesin sortir yang efisien, karena hashing mencampur setiap pemesanan.

Daftar tertaut ganda

Daftar tertaut ganda dapat dilihat sebagai bagian dari tumpukan di mana item pertama memiliki prioritas terbesar, jadi mari kita bandingkan mereka di sini juga:

• insersi:
  • posisi:
    • daftar tertaut dua kali lipat: item yang dimasukkan harus merupakan yang pertama atau terakhir, karena kami hanya memiliki pointer ke elemen-elemen itu.
    • tumpukan biner: item yang dimasukkan dapat berakhir pada posisi apa pun. Kurang membatasi daripada daftar tertaut.
  • waktu:
    • daftar tertaut ganda: O(1)kasus terburuk karena kami memiliki petunjuk ke item, dan pembaruannya sangat sederhana
    • biner heap: O(1)rata-rata, jadi lebih buruk dari daftar tertaut. Tradeoff untuk memiliki posisi penyisipan yang lebih umum.
• cari: O(n)untuk keduanya

Kasus penggunaan untuk ini adalah ketika kunci tumpukan adalah cap waktu saat ini: dalam kasus itu, entri baru akan selalu pergi ke awal daftar. Jadi kita bahkan bisa melupakan timestamp yang tepat sama sekali, dan hanya menjaga posisi dalam daftar sebagai prioritas.

Ini dapat digunakan untuk mengimplementasikan cache LRU . Sama seperti untuk menumpuk aplikasi seperti Dijkstra , Anda ingin menyimpan hashmap tambahan dari kunci ke simpul yang sesuai dari daftar, untuk menemukan simpul mana yang akan diperbarui dengan cepat.

Perbandingan BST Seimbang yang berbeda

Meskipun memasukkan asimtotik dan menemukan waktu untuk semua struktur data yang umumnya diklasifikasikan sebagai "BST Seimbang" yang saya lihat sejauh ini adalah sama, BBST yang berbeda memiliki trade-off yang berbeda. Saya belum sepenuhnya mempelajari ini, tetapi akan lebih baik untuk meringkas trade-off ini di sini:

• Pohon merah-hitam . Tampaknya menjadi BBST yang paling umum digunakan pada 2019, misalnya BBST yang digunakan oleh implementasi GCC 8.3.0 C ++
• Pohon AVL . Tampaknya sedikit lebih seimbang daripada BST, jadi bisa lebih baik untuk menemukan latensi, dengan biaya penemuan yang sedikit lebih mahal. Wiki meringkas: "Pohon AVL sering dibandingkan dengan pohon merah-hitam karena keduanya mendukung rangkaian operasi yang sama dan meluangkan waktu yang sama untuk operasi dasar. Untuk aplikasi pencarian intensif, pohon AVL lebih cepat daripada pohon merah-hitam karena mereka lebih seimbang. Mirip dengan pohon merah-hitam, pohon AVL seimbang tinggi. Keduanya, secara umum, tidak seimbang berat atau seimbang untuk setiap mu <1/2; yaitu, saudara kandung node dapat memiliki sangat besar jumlah keturunan yang berbeda. "
• WAVL . The kertas asli menyebutkan keuntungan dari versi yang dalam hal batas pada operasi rebalancing dan rotasi.

Lihat juga

Pertanyaan serupa tentang CS: /cs/27860/whats-the-difference-between-a-binary-search-tree-and-a-binary-heap

Heap hanya menjamin bahwa elemen pada level yang lebih tinggi lebih besar (untuk max-heap) atau lebih kecil (untuk min-heap) daripada elemen pada level yang lebih rendah, sedangkan BST menjamin pesanan (dari "kiri" ke "kanan"). Jika Anda ingin elemen yang diurutkan, gunakan BST.

Kapan menggunakan heap dan kapan menggunakan BST

Heap lebih baik di findMin / findMax ( O(1)), sedangkan BST bagus di semua ditemukan ( O(logN)). Masukkan adalah O(logN)untuk kedua struktur. Jika Anda hanya peduli dengan findMin / findMax (mis. Terkait prioritas), lanjutkan dengan heap. Jika Anda ingin semuanya diurutkan, gunakan BST.

Beberapa slide pertama dari sini menjelaskan dengan sangat jelas.

Seperti yang disebutkan oleh orang lain, Heap dapat melakukan findMin atau findMax di O (1) tetapi tidak keduanya dalam struktur data yang sama. Namun saya tidak setuju bahwa Heap lebih baik di findMin / findMax. Bahkan, dengan sedikit modifikasi, BST dapat melakukan keduanya findMin dan findMax di O (1).

Dalam BST yang dimodifikasi ini, Anda melacak min node dan max node setiap kali Anda melakukan operasi yang berpotensi mengubah struktur data. Misalnya dalam operasi penyisipan Anda dapat memeriksa apakah nilai min lebih besar dari nilai yang baru dimasukkan, lalu tetapkan nilai min ke simpul yang baru ditambahkan. Teknik yang sama dapat diterapkan pada nilai maksimal. Karenanya, BST ini mengandung informasi ini yang dapat Anda ambil di O (1). (sama seperti tumpukan biner)

Dalam BST ini (BST Seimbang), ketika Anda pop minatau pop max, nilai min berikutnya yang akan ditetapkan adalah penerus dari simpul min, sedangkan nilai maks berikutnya yang akan ditugaskan adalah pendahulu dari simpul maks. Jadi itu tampil di O (1). Namun kita perlu menyeimbangkan kembali pohon, sehingga masih akan menjalankan O (log n). (sama seperti tumpukan biner)

Saya akan tertarik mendengar pemikiran Anda dalam komentar di bawah ini. Terima kasih :)

Memperbarui

Referensi silang ke pertanyaan serupa Bisakah kita menggunakan pohon pencarian biner untuk mensimulasikan operasi heap? untuk diskusi lebih lanjut tentang simulasi Heap menggunakan BST.

Pohon pencarian biner menggunakan definisi: bahwa untuk setiap simpul, simpul di sebelah kiri memiliki nilai lebih kecil (kunci) dan simpul di sebelah kanannya memiliki nilai lebih besar (kunci).

Sedangkan heap, menjadi implementasi pohon biner menggunakan definisi berikut:

Jika A dan B adalah simpul, di mana B adalah simpul anak dari A, maka nilai (kunci) A harus lebih besar dari atau sama dengan nilai (kunci) B. Artinya, kunci (A) ≥ kunci (B ).

http://wiki.answers.com/Q/Difference_between_binary_search_tree_and_heap_tree

Saya berlari dalam pertanyaan yang sama hari ini untuk ujian saya dan saya sudah benar. tersenyumlah ... :)

Penggunaan lain BST atas Heap; karena perbedaan penting:

• menemukan penerus dan pendahulu dalam BST akan membutuhkan waktu O (h). (O (logn) dalam BST seimbang)
• sementara di Heap, akan membutuhkan O (n) waktu untuk menemukan penerus atau pendahulu beberapa elemen.

Penggunaan BST di atas Heap : Sekarang, mari kita katakan kita menggunakan struktur data untuk menyimpan waktu pendaratan penerbangan. Kami tidak dapat menjadwalkan penerbangan ke darat jika perbedaan waktu pendaratan kurang dari 'd'. Dan anggap banyak penerbangan telah dijadwalkan mendarat dalam struktur data (BST atau Heap).

Sekarang, kami ingin menjadwalkan Penerbangan lain yang akan mendarat di t . Oleh karena itu, kita perlu menghitung selisih t dengan penggantinya dan pendahulunya (harus> d). Jadi, kita akan membutuhkan BST untuk ini, yang melakukannya dengan cepat yaitu di O (logn) jika seimbang.

Diedit:

Menyortir BST membutuhkan O (n) waktu untuk mencetak elemen dalam urutan yang diurutkan (Inorder traversal), sementara Heap dapat melakukannya dalam waktu O (n logn). Heap mengekstrak elemen min dan mem-reap array, yang membuatnya melakukan pengurutan dalam waktu O (n logn).

Masukkan semua elemen n dari array ke BST mengambil O (n logn). n elemnts dalam array dapat dimasukkan ke heap dalam waktu O (n). Yang memberi banyak keuntungan

Heap hanya menjamin bahwa elemen pada level yang lebih tinggi lebih besar (untuk max-heap) atau lebih kecil (untuk min-heap) daripada elemen pada level yang lebih rendah

Saya suka jawaban di atas dan memberikan komentar saya lebih spesifik untuk kebutuhan dan penggunaan saya. Saya harus mendapatkan daftar lokasi n menemukan jarak dari setiap lokasi ke titik tertentu katakan (0,0) dan kemudian kembali lokasi saya memiliki jarak yang lebih kecil. Saya menggunakan Antrian Prioritas yang Heap. Untuk menemukan jarak dan meletakkan tumpukan, saya butuh n (log (n)) n-lokasi log (n) setiap penyisipan. Kemudian untuk mendapatkan m dengan jarak terpendek dibutuhkan m (log (n)) m-lokasi log (n) penghapusan penumpukan.

Saya jika harus melakukan ini dengan BST, itu akan membawa saya n (n) kasus terburuk. (Katakan nilai pertama sangat kecil dan semua lainnya datang secara berurutan lebih lama dan lebih lama dan pohon merentang ke kanan anak saja atau anak kiri dalam kasus yang lebih kecil dan lebih kecil. min akan mengambil O (1) waktu tetapi sekali lagi saya harus menyeimbangkan. Jadi dari situasi saya dan semua jawaban di atas apa yang saya dapatkan adalah ketika Anda hanya setelah nilai pada min atau basis prioritas max pergi untuk tumpukan