Tumpukan biner

Tumpukan biner adalah struktur data tumpukan yang berbentuk pohon biner . Tumpukan biner
adalah cara umum untuk mengimplementasikan antrean prioritas . [ 1 ] : 162–163 Tumpukan biner
diperkenalkan oleh JWJ Williams pada tahun 1964 sebagai struktur data untuk
mengimplementasikan heapsort . [ 2 ]

Tumpukan biner (min)

Jenis pohon
biner/tumpukan

Ditemukan Tahun 1964

Diciptakan oleh JWJ Williams

Kompleksitas waktu dalam notasi O besar

Operasi Rata-rata Kasus

terburuk
Contoh tumpukan biner maks lengkap

Menyisipkan O(1) Logaritma

n​

Temukan-min O(1) O(1)

Hapus-min Logaritma Logaritma

n​ n​
Contoh tumpukan min biner lengkap
Tombol penurunan Logaritma Logaritma
Tumpukan biner didefinisikan sebagai pohon
n​ n​
[3]
biner dengan dua kendala tambahan:
Menggabungkan Pada )​ Pada )​
Properti bentuk: tumpukan biner merupakan
pohon biner lengkap ; artinya, semua Kompleksitas ruang
tingkatan pohon, kecuali mungkin yang
terakhir (terdalam) terisi penuh, dan, jika
tingkatan terakhir pohon tidak lengkap, simpul-simpul pada tingkatan tersebut terisi dari kiri ke
kanan.

Properti tumpukan: kunci yang disimpan dalam setiap simpul lebih besar atau sama dengan
(≥) atau lebih kecil atau sama dengan (≤) kunci pada anak simpul, menurut urutan total
tertentu .

Tumpukan yang kunci induknya lebih besar atau sama dengan (≥) kunci anak disebut tumpukan
maksimum ; tumpukan yang kunci induknya lebih kecil atau sama dengan (≤) disebut tumpukan
minimum . Algoritma yang efisien (yaitu, waktu logaritmik ) dikenal untuk dua operasi yang
diperlukan untuk mengimplementasikan antrean prioritas pada tumpukan biner:

Memasukkan elemen;

Menghapus elemen terkecil atau terbesar dari (masing-masing) tumpukan minimum atau
tumpukan maksimum.

Tumpukan biner juga umum digunakan dalam algoritma penyortiran heapsort , yang merupakan
algoritma di tempat karena tumpukan biner dapat diimplementasikan sebagai struktur data
implisit , menyimpan kunci dalam sebuah array dan menggunakan posisi relatifnya dalam array
itu untuk merepresentasikan hubungan anak–induk.

Operasi tumpukan

Baik operasi penyisipan maupun penghapusan memodifikasi heap untuk mempertahankan

properti bentuk terlebih dahulu, dengan menambahkan atau menghapus dari ujung heap.
Kemudian properti heap dipulihkan dengan menelusuri ke atas atau ke bawah heap. Kedua
operasi tersebut membutuhkan waktu O(log n ) .

Menyisipkan

Untuk memasukkan elemen ke dalam tumpukan, kita melakukan langkah-langkah berikut:

1. Tambahkan elemen ke tingkat bawah tumpukan di ruang terbuka paling kiri.

2. Bandingkan elemen yang ditambahkan dengan induknya; jika urutannya benar, hentikan.

3. Jika tidak, tukar elemen dengan induknya dan kembali ke langkah sebelumnya.

Langkah 2 dan 3, yang memulihkan properti heap dengan membandingkan dan mungkin
menukar node dengan induknya, disebut operasi up-heap (juga dikenal sebagai bubble-up ,
percolate-up , sift-up , trickle-up , swim-up , heapify-up , cascade-up , atau fix-up ).

Jumlah operasi yang diperlukan hanya bergantung pada jumlah level yang harus dicapai elemen
baru untuk memenuhi properti heap. Dengan demikian, operasi penyisipan memiliki
kompleksitas waktu kasus terburuk sebesar O(log n ) . Untuk heap acak, dan untuk penyisipan
berulang, operasi penyisipan memiliki kompleksitas kasus rata-rata sebesar O(1). [ 4 ] [ 5 ]

Sebagai contoh penyisipan tumpukan biner, katakanlah kita memiliki tumpukan maksimum
dan kita ingin menambahkan angka 15 ke dalam tumpukan. Pertama-tama kita tempatkan angka
15 di posisi yang ditandai oleh X. Akan tetapi, properti tumpukan dilanggar karena 15 > 8 , jadi
kita perlu menukar angka 15 dan 8. Jadi, tumpukan terlihat seperti berikut setelah pertukaran
pertama:

Namun properti heap masih dilanggar karena 15 > 11 , jadi kita perlu menukar lagi:

yang merupakan max-heap yang valid. Tidak perlu memeriksa anak kiri setelah langkah terakhir
ini: pada awalnya, max-heap valid, artinya akarnya sudah lebih besar dari anak kirinya, jadi
mengganti akar dengan nilai yang lebih besar akan mempertahankan properti bahwa setiap
simpul lebih besar dari anak-anaknya ( 11 > 5 ; jika 15 > 11 , dan 11 > 5 , maka 15 > 5 , karena
hubungan transitif ).

Ekstrak

Prosedur untuk menghapus akar dari tumpukan (secara efektif mengekstraksi elemen
maksimum dalam tumpukan maksimum atau elemen minimum dalam tumpukan minimum)
sambil mempertahankan properti tumpukan adalah sebagai berikut:

1. Ganti akar tumpukan dengan elemen terakhir pada level terakhir.

2. Bandingkan akar baru dengan anak-anaknya; jika urutannya benar, hentikan.

3. Jika tidak, tukar elemen tersebut dengan salah satu anaknya dan kembali ke langkah
sebelumnya. (Tukar dengan anaknya yang lebih kecil di tumpukan minimum dan anaknya
yang lebih besar di tumpukan maksimum.)

Langkah 2 dan 3, yang memulihkan properti heap dengan membandingkan dan mungkin
menukar sebuah node dengan salah satu anaknya, disebut operasi down-heap (juga dikenal
sebagai bubble-down , percolate-down , sift-down , sink-down , trickle down , heapify-down ,
cascade-down , fix-down , extract-min atau extract-max , atau cukup heapify ).

Jadi, jika kita memiliki tumpukan maksimum yang sama seperti sebelumnya
Kita hilangkan angka 11 dan ganti dengan angka 4.

Sekarang properti heap dilanggar karena 8 lebih besar dari 4. Dalam kasus ini, menukar dua
elemen, 4 dan 8, sudah cukup untuk memulihkan properti heap dan kita tidak perlu menukar
elemen lebih lanjut:

Node yang bergerak ke bawah ditukar dengan node anak yang lebih besar dalam tumpukan
maksimum (dalam tumpukan minimum, node tersebut akan ditukar dengan node anak yang
lebih kecil), hingga node tersebut memenuhi properti tumpukan di posisi barunya. Fungsionalitas
ini dicapai oleh fungsi Max-Heapify sebagaimana didefinisikan di bawah ini dalam pseudocode
untuk tumpukan A yang didukung array dengan panjang length ( A ). A diindeks mulai dari 1.

// Lakukan operasi down-heap atau heapify-down untuk max-heap

// A : array yang mewakili tumpukan, diindeks mulai dari 1
// i : indeks untuk memulai ketika melakukan heapifikasi ke bawah
Max-Heapify ( A , i ):
kiri ← 2× i
kanan ← 2× i + 1
terbesar ← i

jika kiri ≤ panjang ( A ) dan A [ kiri ] > A [ terbesar ]

maka :
terbesar ← kiri

jika kanan ≤ panjang ( A ) dan A [ kanan ] > A [ terbesar ]

maka :
terbesar ← kanan
 jika terbesar ≠ i maka :
tukar A [ i ] dan A [ terbesar ]
Max-Heapify ( A , terbesar )

Agar algoritme di atas dapat melakukan heapifikasi ulang array dengan benar, tidak ada simpul
selain simpul pada indeks i dan dua anak langsungnya yang dapat melanggar properti heap.
Operasi down-heap (tanpa swap sebelumnya) juga dapat digunakan untuk mengubah nilai akar,
bahkan saat suatu elemen tidak sedang dihapus.

Dalam kasus terburuk, akar baru harus ditukar dengan anaknya di setiap level hingga mencapai
level terbawah tumpukan, artinya operasi penghapusan memiliki kompleksitas waktu relatif
terhadap tinggi pohon, atau O(log n ).

Masukkan lalu ekstrak

Memasukkan elemen lalu mengekstraknya dari tumpukan dapat dilakukan lebih efisien daripada
sekadar memanggil fungsi insert dan extract yang didefinisikan di atas, yang akan melibatkan
operasi upheap dan downheap . Sebagai gantinya, kita dapat melakukan downheap operasi
saja, seperti berikut:

1. Bandingkan apakah item yang kita dorong atau bagian atas tumpukan yang mengintip lebih
besar (dengan asumsi tumpukan maksimum)

2. Jika akar tumpukan lebih besar:

1. Ganti root dengan item baru

2. Down-heapify dimulai dari akarnya

3. Jika tidak, kembalikan barang yang kami dorong

Python menyediakan fungsi semacam itu untuk penyisipan lalu ekstraksi yang disebut
"heappushpop", yang diparafrasekan di bawah ini. [ 6 ] [ 7 ] Array heap diasumsikan memiliki
elemen pertamanya pada indeks 1.

// Dorong item baru ke tumpukan (maks) dan kemudian ekstrak akar

tumpukan yang dihasilkan.
// heap : sebuah array yang mewakili heap, diindeks pada 1
// item : elemen yang akan disisipkan
// Mengembalikan angka yang lebih besar dari dua angka antara item
dan akar dari heap .
Push-Pop ( heap : List<T>, item : T) -> T:
 jika heap tidak kosong dan heap[1] > item maka : // < jika
min heap
tukar heap [1] dan item
_downheap( heap dimulai dari indeks 1)
kembalikan item

Fungsi serupa dapat didefinisikan untuk memunculkan dan kemudian memasukkan, yang dalam
Python disebut "heapreplace":

// Ekstrak akar tumpukan, dan dorong item baru

// heap : sebuah array yang mewakili heap, diindeks pada 1
// item : elemen yang akan disisipkan
// Mengembalikan akar heap saat ini
Ganti ( heap : List<T>, item : T) -> T:
tukar heap [1] dan item
_downheap( heap dimulai dari indeks 1)
kembalikan item

Mencari

Menemukan suatu elemen sembarangan memerlukan waktu O(n).

Menghapus

Menghapus elemen sembarangan dapat dilakukan sebagai berikut:

1. Temukan indeksnya dari elemen yang ingin kita hapus

2. Tukar elemen ini dengan elemen terakhir. Hapus elemen terakhir setelah pertukaran.

3. Down-heapify atau up-heapify untuk mengembalikan properti heap. Dalam max-heap (min-
heap), up-heapify hanya diperlukan ketika kunci elemen baru lebih besar (lebih kecil) dari
yang sebelumnya karena hanya properti tumpukan dari elemen induk yang mungkin
dilanggar. Dengan asumsi bahwa properti tumpukan berlaku antara elemen dan anak-
anaknya sebelum pertukaran elemen, maka tidak dapat dilanggar oleh nilai kunci yang
sekarang lebih besar (lebih kecil). Ketika kunci yang baru lebih kecil (lebih besar) dari yang
sebelumnya, maka hanya diperlukan down-heapify karena properti heap mungkin hanya
dilanggar pada elemen anak.
Mengurangi atau menambah kunci

Operasi kunci penurunan mengganti nilai suatu simpul dengan nilai tertentu dengan nilai yang
lebih rendah, dan operasi kunci kenaikan melakukan hal yang sama tetapi dengan nilai yang lebih
tinggi. Ini melibatkan pencarian simpul dengan nilai yang diberikan, mengubah nilai, dan
kemudian melakukan penimbunan ke bawah atau ke atas untuk memulihkan properti tumpukan.

Penurunan kunci dapat dilakukan sebagai berikut:

1. Temukan indeks elemen yang ingin kita modifikasi

2. Kurangi nilai node

3. Down-heapify (dengan asumsi heap maksimum) untuk memulihkan properti heap

Peningkatan kunci dapat dilakukan sebagai berikut:

1. Temukan indeks elemen yang ingin kita modifikasi

2. Meningkatkan nilai node

3. Up-heapify (dengan asumsi tumpukan maksimal) untuk memulihkan properti tumpukan

Membangun tumpukan

Membangun heap dari array n elemen input dapat dilakukan dengan memulai dengan heap
kosong, kemudian memasukkan setiap elemen secara berurutan. Pendekatan ini, yang disebut
metode Williams berdasarkan penemu heap biner, mudah terlihat berjalan dalam waktu
O ( n log n ) : ia melakukan n penyisipan pada biaya O (log n ) masing-masing. [ a ]

Namun, metode Williams kurang optimal. Metode yang lebih cepat (karena Floyd [ 8 ] ) dimulai
dengan meletakkan elemen-elemen pada pohon biner secara sembarangan, dengan
menghormati properti bentuk (pohon dapat direpresentasikan oleh sebuah array, lihat di bawah).
Kemudian mulai dari level terendah dan bergerak ke atas, menyaring akar dari setiap sub-pohon
ke bawah seperti pada algoritma penghapusan hingga properti tumpukan dipulihkan. Lebih
khusus lagi jika semua sub-pohon dimulai pada ketinggian tertentu sudah “ditumpuk” (tingkat
paling bawah sesuai dengan ), pohon-pohon pada ketinggian dapat ditumpuk dengan
mengirimkan akarnya ke sepanjang jalur anak-anak yang bernilai maksimum ketika membangun
tumpukan maksimum, atau anak-anak yang bernilai minimum ketika membangun tumpukan
minimum. Proses ini berlangsung operasi (swap) per node. Dalam metode ini sebagian
besar heapifikasi terjadi di level yang lebih rendah. Karena tinggi heap adalah , jumlah

node pada ketinggian adalah Oleh karena itu, biaya untuk menumpuk semua

sub-pohon adalah:
Ini menggunakan fakta bahwa seri tak terbatas yang diberikan konvergen .

Nilai pasti di atas (angka perbandingan terburuk selama konstruksi tumpukan) diketahui sama
dengan:

Bahasa Indonesia : , [ 9 ] [ b ]

di mana s ( n ) adalah jumlah semua digit representasi biner n dan e 2 n ) adalah eksponen 2
2 (
dalam faktorisasi prima n .

Kasus rata-rata lebih rumit untuk dianalisis, namun dapat ditunjukkan untuk mendekati
perbandingan 1,8814 n − 2 log n + O (1) secara asimtotik . [ 10 ] [ 11 ]
2

Fungsi Build-Max-Heap yang mengikuti, mengonversi array A yang menyimpan pohon biner
lengkap dengan n node ke max-heap dengan berulang kali menggunakan Max-Heapify (down-
heapify untuk max-heap) dengan cara bottom-up. Elemen array yang diindeks oleh
floor ( n /2) + 1 , floor ( n /2) + 2 , ..., n semuanya adalah daun untuk pohon (dengan asumsi
bahwa indeks dimulai pada 1)—jadi masing-masing adalah heap satu elemen, dan tidak perlu di-
down-heapifikasi. Build-Max-Heap menjalankan Max-Heapify pada masing-masing node pohon
yang tersisa.

Build-Max-Heap ( A ):
untuk setiap indeks i dari lantai ( panjang ( A )/2) hingga
1 lakukan:
Max-Heapify ( A , i )

Implementasi tumpukan

Pohon biner kecil lengkap yang disimpan dalam sebuah array

 Perbandingan antara tumpukan biner dan implementasi array.

Heap biasanya diimplementasikan dengan array . Setiap pohon biner dapat disimpan dalam
array, tetapi karena heap biner selalu merupakan pohon biner lengkap, heap dapat disimpan
secara kompak. Tidak diperlukan ruang untuk pointer ; sebagai gantinya, induk dan anak dari
setiap node dapat ditemukan dengan aritmatika pada indeks array. Properti ini menjadikan
implementasi heap ini sebagai contoh sederhana dari struktur data implisit atau daftar
Ahnentafel . Detailnya bergantung pada posisi akar, yang pada gilirannya dapat bergantung pada
batasan bahasa pemrograman yang digunakan untuk implementasi, atau preferensi
programmer. Secara khusus, terkadang akar ditempatkan pada indeks 1, untuk
menyederhanakan aritmatika.

Misalkan n adalah jumlah elemen dalam tumpukan dan i adalah indeks valid sembarang dari
array yang menyimpan tumpukan. Jika akar pohon berada pada indeks 0, dengan indeks valid 0
hingga n − 1, maka setiap elemen a pada indeks i memiliki

anak-anak pada indeks 2 i + 1 dan 2 i + 2

induknya pada indeks lantai (( i − 1) / 2).

Atau, jika akar pohon berada pada indeks 1, dengan indeks valid 1 hingga n , maka setiap elemen
a pada indeks i memiliki

anak pada indeks 2 i dan 2 i +1

induknya pada indeks lantai ( i /2).

Implementasi ini digunakan dalam algoritma heapsort yang menggunakan kembali ruang yang
dialokasikan ke array input untuk menyimpan heap (yaitu algoritma dilakukan di tempat ).
Implementasi ini juga berguna sebagai antrian Prioritas . Ketika array dinamis digunakan,
penyisipan item dalam jumlah tak terbatas dimungkinkan.

Operasi upheap or downheap kemudian dapat dinyatakan dalam bentuk array sebagai berikut:
misalkan properti heap berlaku untuk indeks b , b +1, ..., e . Fungsi sift-down memperluas
properti heap ke b −1, b , b +1, ..., e . Hanya indeks i = b −1 yang dapat melanggar properti heap.
Biarkan j menjadi indeks anak terbesar dari a [ i ] (untuk max-heap, atau anak terkecil untuk min-
heap) dalam rentang b , ..., e . (Jika tidak ada indeks seperti itu karena 2 i > e maka properti heap
berlaku untuk rentang yang baru diperluas dan tidak ada yang perlu dilakukan.) Dengan menukar
nilai a [ i ] dan a [ j ] properti heap untuk posisi i ditetapkan. Pada titik ini, satu-satunya masalah
adalah bahwa properti heap mungkin tidak berlaku untuk indeks j . Fungsi sift-down diterapkan
secara tail-rekursif ke indeks j hingga properti heap ditetapkan untuk semua elemen.

Fungsi sift-down cepat. Pada setiap langkah, hanya diperlukan dua perbandingan dan satu
pertukaran. Nilai indeks tempat ia bekerja berlipat ganda pada setiap iterasi, sehingga paling
banyak diperlukan langkah log e .
2

Untuk tumpukan besar dan penggunaan memori virtual , menyimpan elemen dalam array sesuai
dengan skema di atas tidaklah efisien: (hampir) setiap level berada di halaman yang berbeda . B-
heap adalah tumpukan biner yang menyimpan sub-pohon dalam satu halaman, sehingga
mengurangi jumlah halaman yang diakses hingga sepuluh kali lipat. [ 12 ]

Operasi penggabungan dua heap biner membutuhkan Θ( n ) untuk heap berukuran sama. Yang
terbaik yang dapat Anda lakukan adalah (dalam kasus implementasi array) cukup
menggabungkan dua array heap dan membangun heap dari hasilnya. [ 13 ] Heap pada elemen n
dapat digabungkan dengan heap pada elemen k menggunakan perbandingan kunci O(log n log k
), atau, dalam kasus implementasi berbasis pointer, dalam waktu O(log n log k ). [ 14 ] Algoritma
untuk membagi heap pada elemen n menjadi dua heap pada elemen k dan nk , masing-masing,
berdasarkan tampilan baru heap sebagai koleksi subheap yang terurut disajikan dalam. [ 15 ]
Algoritma membutuhkan perbandingan O(log n * log n ). Tampilan tersebut juga menyajikan
algoritma baru dan sederhana secara konseptual untuk menggabungkan heap. Jika
penggabungan merupakan tugas umum, implementasi tumpukan yang berbeda
direkomendasikan, seperti tumpukan binomial , yang dapat digabungkan dalam O(log n ).

Selain itu, tumpukan biner dapat diimplementasikan dengan struktur data pohon biner
tradisional, tetapi ada masalah dengan menemukan elemen yang berdekatan pada level terakhir
pada tumpukan biner saat menambahkan elemen. Elemen ini dapat ditentukan secara algoritmik
atau dengan menambahkan data tambahan ke node, yang disebut "threading" pohon—alih-alih
hanya menyimpan referensi ke anak-anak, kami juga menyimpan penerus inorder node.

Dimungkinkan untuk memodifikasi struktur tumpukan untuk membuat ekstraksi elemen terkecil
dan terbesar menjadi mungkin waktu. [ 16 ] Untuk melakukan ini, baris-baris bergantian
antara tumpukan min dan tumpukan maks. Algoritmenya kurang lebih sama, tetapi, pada setiap
langkah, seseorang harus mempertimbangkan baris-baris yang bergantian dengan perbandingan
yang bergantian. Kinerjanya kurang lebih sama dengan tumpukan arah tunggal yang normal. Ide
ini dapat digeneralisasikan ke tumpukan min-maks-median.

Turunan persamaan indeks

Dalam heap berbasis array, anak dan induk dari sebuah node dapat ditemukan melalui aritmatika
sederhana pada indeks node tersebut. Bagian ini menguraikan persamaan yang relevan untuk
heap dengan akarnya pada indeks 0, dengan catatan tambahan tentang heap dengan akarnya
pada indeks 1.

Untuk menghindari kebingungan, kami mendefinisikan level suatu node sebagai jaraknya dari
akar, sehingga akar itu sendiri menempati level 0.

Node anak

Untuk node umum yang terletak pada indeks i (mulai dari 0), pertama-tama kita akan
memperoleh indeks anak kanannya, .

Biarkan node i berada di level L , dan perhatikan bahwa setiap level l berisi tepat node. Selain
itu, ada juga node yang terdapat dalam lapisan hingga dan termasuk lapisan l (pikirkan
aritmatika biner; 0111...111 = 1000...000 - 1). Karena akar disimpan pada 0, node ke- k akan
disimpan pada indeks Dengan menggabungkan semua pengamatan ini akan diperoleh
ekspresi berikut untuk indeks node terakhir di lapisan l .

Misalkan ada j node setelah node i di lapisan L, sehingga

Setiap j node ini harus memiliki tepat 2 anak, jadi harus ada simpul yang memisahkan anak
kanan i dari akhir lapisannya ( ).

Dengan memperhatikan bahwa anak kiri dari setiap node selalu berada 1 tempat sebelum anak
kanannya, kita memperoleh .

Jika akarnya terletak pada indeks 1 bukan 0, maka simpul terakhir pada setiap level akan berada
pada indeks Menggunakan ini secara menyeluruh menghasilkan Dan
untuk tumpukan dengan akar di 1.

Node induk

Setiap simpul non-akar merupakan anak kiri atau kanan dari induknya, sehingga salah satu dari
berikut ini harus berlaku:
Karena itu,

Sekarang perhatikan ekspresi .

Jika simpul adalah anak kiri, ini memberikan hasil segera, namun, ini juga memberikan hasil
yang benar jika node adalah anak yang tepat. Dalam hal ini, harus seimbang, dan
karenanya pasti aneh.

Oleh karena itu, terlepas dari apakah suatu simpul merupakan anak kiri atau kanan, induknya
dapat ditemukan dengan ekspresi:

Struktur terkait

Karena urutan saudara kandung dalam heap tidak ditentukan oleh properti heap, dua anak dari
satu node dapat dipertukarkan secara bebas kecuali jika hal itu melanggar properti shape
(bandingkan dengan treap ). Namun, perlu dicatat bahwa dalam heap berbasis array yang umum,
menukar anak-anak mungkin juga mengharuskan pemindahan node sub-pohon anak-anak untuk
mempertahankan properti heap.

Tumpukan biner adalah kasus khusus dari tumpukan d-ary di mana d = 2.

Ringkasan waktu berjalan

Berikut adalah kompleksitas waktu [ 17 ] dari berbagai struktur data heap. Singkatan am.
menunjukkan bahwa kompleksitas yang diberikan diamortisasi, jika tidak maka kompleksitas
tersebut adalah kompleksitas kasus terburuk. Untuk arti dari " O ( f )" dan " Θ ( f )" lihat notasi Big
O. Nama-nama operasi mengasumsikan min-heap.
 temukan- penurunan- membuat
Operasi hapus-min menyisipkan menggabungkan
min kunci tumpukan [ c ]

Logaritma
Biner [ 17 ] Aku (1) Logaritma n​ Logaritma n​ dan ( n ) dan ( n )
n​

O (log n ) O (log n ) O (log n )

Miring [ 18 ] Aku (1) O (log n ) saya. Θ ( n ) saya.
saya. saya. saya.

Logaritma
Kiri [ 19 ] Aku (1) Logaritma n​ Logaritma n​ Logaritma n​ dan ( n )
n​

Logaritma Bahasa Indonesia: Θ

Binomial [ 17 ] [ 21 ] Aku (1) Logaritma n​ Aku (1) pagi. dan ( n )
n​ (log n ) [ d ]

Binomial miring Logaritma Bahasa Indonesia: Θ

[ 22 ]
Aku (1) Logaritma n​​ Aku (1) dan ( n )
n​ (log n ) [ d ]

2–3 tumpukan O (log n ) Bahasa Indonesia: O

[ 24 ] Aku (1) Aku (1) Aku (1) pagi. dan ( n )
saya. (log n ) [ d ]

Kemiringan bawah O (log n ) O (log n )

[ 18 ]
Aku (1) Aku (1) pagi. Aku (1) pagi. Θ ( n ) saya.
ke atas saya. saya.

O (log n ) o (log n )
Pasangan [ 25 ] Aku (1) Aku (1) Aku (1) dan ( n )
saya. saya. [ e ]

Pasangan O (log n )
[ 28 ]
Aku (1) Aku (1) pagi. Aku (1) Aku (1) dan ( n )
peringkat saya.

O (log n )
Fibonacci [ 17 ] [ 29 ] Aku (1) Aku (1) pagi. Aku (1) Aku (1) dan ( n )
saya.

Fibonacci Ketat Logaritma

[ 30 ] [ f ] Aku (1) Aku (1) Aku (1) Aku (1) dan ( n )
n​​

Logaritma
Brodal [ 31 ] [ f ] Aku (1) Aku (1) Aku (1) Aku (1) Tidak ( n ) [ 32 ]
n​

a. Faktanya, prosedur ini dapat ditunjukkan membutuhkanwaktu Θ( n log n ) dalam kasus

terburuk , yang berarti bahwa n log n juga merupakan batas bawah asimptotik pada
kompleksitas. [ 1 ] : 167 Dalam kasus rata-rata (merata-ratakan semua permutasi dari n
masukan), metode ini membutuhkan waktu linier. [ 8 ]

b. Ini tidak berarti bahwa penyortiran dapat dilakukan dalam waktu linier karena membangun
tumpukan hanya langkah pertama dari algoritma heapsort .

c. make-heap adalah operasi membangun heap dari urutan n elemen yang tidak diurutkan. Hal
ini dapat dilakukan dalamwaktu Θ ( n ) setiap kali meld berjalan dalam waktu O (log n ) (di
mana kedua kompleksitas dapat diamortisasi). [ 18 ] [ 19 ] Algoritma lain mencapai Θ ( n )
untuk heap biner. [ 20 ]

d. Untuk tumpukan persisten (tidak mendukung decrease-key ), transformasi generik

mengurangi biaya meld ke insert , sementara biaya baru delete-min adalah jumlah biaya
 delete-min dan meld yang lama . [ 23 ] Di sini, ia membuat meld berjalan dalam waktu Θ (1)
(diamortisasi, jika biaya insert adalah) sementara delete-min masih berjalan dalam O (log n
). Diterapkan pada tumpukan binomial miring, ia menghasilkan antrean Brodal-Okasaki,
tumpukan persisten dengan kompleksitas kasus terburuk yang optimal. [ 22 ]

[ 26 ] [ 27 ]
e. Batas bawah batas atas

f. Antrean Brodal dan tumpukan Fibonacci yang ketat mencapai kompleksitas kasus terburuk
yang optimal untuk tumpukan. Keduanya pertama kali dideskripsikan sebagai struktur data
imperatif. Antrean Brodal-Okasaki adalah struktur data persisten yang mencapai optimum
yang sama, kecuali bahwa kunci penurunan tidak didukung.

Referensi

1. , Thomas .; Leiserson, Charles E .; Rivest, Ronald L .; Stein, Clifford (2009) [1990]. Pengantar
Algoritma (Edisi ke-3rd). MIT Press dan McGraw-Hill. ISBN Nomor telepon 0-262-03384-4.

2. Williams, JWJ (1964), "Algoritma 232 - Heapsort", Komunikasi ACM , 7 (6): 347– 348, doi :
10.1145/512274.512284 ([Link]

3. Y Narahari, "Binary Heaps" ([Link] , Struktur Data

dan Algoritma ([Link]

4. Porter, Thomas; Simon, Istvan (Sep 1975). "Penyisipan acak ke dalam struktur antrian
prioritas". Transaksi IEEE pada Rekayasa Perangkat Lunak . SE-1 (3): 292– 298. doi :
10.1109/TSE.1975.6312854 ([Link] . ISSN
1939-3520 ([Link] . S2CID 18907513 ([Link]
[Link]/CorpusID:18907513) .

5. Mehlhorn, Kurt; Tsakalidis, A. (Feb 1989). "Struktur data" ([Link]

[Link]/handle/20.500.11880/26179) . Universität des Saarlandes : 27. doi :
10.22028/D291-26123 ([Link] . "Porter dan Simon
[171] menganalisis biaya rata-rata penyisipan elemen acak ke dalam tumpukan acak dalam
hal pertukaran. Mereka membuktikan bahwa rata-rata ini dibatasi oleh konstanta 1,61. Bukti
mereka tidak dapat digeneralisasi ke urutan penyisipan karena penyisipan acak ke dalam
tumpukan acak tidak membuat tumpukan acak. Masalah penyisipan berulang diselesaikan
oleh Bollobas dan Simon [27]; mereka menunjukkan bahwa jumlah pertukaran yang
diharapkan dibatasi oleh 1,7645. Biaya terburuk penyisipan dan penghapusan dipelajari oleh
Gonnet dan Munro [84]; mereka memberikan batas log log n + O(1) dan log n + log n* + O(1)
untuk jumlah perbandingan masing-masing."

6. "python/cpython/[Link]" ([Link]
y) . GitHub . Diperoleh pada 2020-08-07 .
 7. "heapq — Algoritma antrean heap — Dokumentasi Python 3.8.5" ([Link]
library/[Link]#[Link]) . [Link] . Diperoleh pada 2020-08-07 .
"[Link](heap, item): Mendorong item pada heap, lalu memunculkan dan
mengembalikan item terkecil dari heap. Tindakan gabungan berjalan lebih efisien daripada
heappush() yang diikuti oleh panggilan terpisah ke heappop()."

8. Hayward, Ryan; McDiarmid, Colin (1991). "Analisis Kasus Rata-rata Pembentukan Heap
dengan Penyisipan Berulang" ([Link]
[Link]/__data/assets/pdf_file/0015/4173/[Link]) (PDF) . J. Algorithms .
12 : 126– 153. CiteSeerX [Link].7888 ([Link]
y?doi=[Link].7888) . doi : 10.1016/0196-6774(91)90027-v ([Link]
F0196-6774%2891%2990027-v) . Diarsipkan dari versi asli ([Link]
ata/assets/pdf_file/0015/4173/[Link]) (PDF) pada 2016-02-05 . Diakses
tanggal 2016-01-28 .

9. Suchenek, Marek A. (2012), "Analisis Kasus Terburuk yang Dasar Namun Tepat dari
Program Konstruksi Tumpukan Floyd" ([Link]
yet-precise-worst-case-analysis-of-floyd-s-heap-50NW30HMxU) , Fundamenta
Informaticae , 120 (1): 75– 92, doi : 10.3233/FI-2012-751 ([Link]
12-751) .

10. Doberkat, Ernst E. (Mei 1984). "Analisis Kasus Rata-rata Algoritma Floyd untuk Membangun
Heaps" ([Link] (PDF) . Informasi dan Kontrol . 6
(2): 114– 131. doi : 10.1016/S0019-9958(84)80053-4 ([Link]
58%2884%2980053-4) .

11. Pasanen, Tomi (November 1996). Analisis Kasus Rata-rata Dasar Algoritma Floyd untuk
Membangun Heap (Laporan teknis). Pusat Ilmu Komputer Turku. CiteSeerX [Link].9526
([Link] . ISBN Telepon 951-
650-888-XLaporan Teknis TUCS No. 64. Perhatikan bahwa makalah ini menggunakan
terminologi asli Floyd "siftup" untuk apa yang sekarang disebut sifting down .

12. Kamp, Poul-Henning (11 Juni 2010). "Anda Melakukannya dengan Salah" ([Link]
org/[Link]?id=1814327) . ACM Queue . Vol. 8, no. 6.

13. Chris L. Kuszmaul. "tumpukan biner" ([Link]

Diarsipkan ([Link]
L/[Link]) 2008-08-08 di Wayback Machine . Kamus Algoritma dan Struktur Data,
Paul E. Black, ed., Institut Nasional Standar dan Teknologi AS. 16 November 2009.

14. J.-R. Sack dan T. Strothotte "Algoritma untuk Menggabungkan Tumpukan" ([Link]
0.1007%2FBF00264229) , Acta Informatica 22, 171-186 (1985).
15. Sack, Jörg-Rüdiger; Strothotte, Thomas (1990). "Karakterisasi tumpukan dan aplikasinya" (h
ttps://[Link]/10.1016%2F0890-5401%2890%2990026-E) . Informasi dan Perhitungan . 86
: 69– 86. doi : 10.1016/0890-5401(90)90026-E ([Link]
0%2990026-E) .

16. Atkinson, MD; J.-R. Sack ; N. Santoro & T. Strothotte (1 Oktober 1986). "Heaps min-max dan
antrian prioritas umum" ([Link]
[Link]/%7Emorin/teaching/5408/refs/[Link]) (PDF) . Teknik pemrograman dan
struktur data. Comm. ACM, 29(10): 996–1000. Diarsipkan dari aslinya ([Link]
[Link]/~morin/teaching/5408/refs/[Link]) (PDF) pada 27 Januari 2007 . Diakses
tanggal 29 April 2008 .

17. Cormen, Thomas H .; Leiserson, Charles E .; Rivest, Ronald L. (1990). Pengantar Algoritma
(Edisi ke-1st). MIT Press dan McGraw-Hill. ISBN Nomor telepon 0-262-03141-8.

18. Sleator, Daniel Dominic ; Tarjan, Robert Endre (Februari 1986). "Tumpukan Penyesuaian Diri"
([Link] . Jurnal SIAM tentang
Komputasi . 15 (1): 52– 69. CiteSeerX [Link].6678 ([Link]
c/summary?doi=[Link].6678) . doi : 10.1137/0215004 ([Link]
15004) . ISSN 0097-5397 ([Link] .

19. Tarjan, Robert (1983). "3.3. Tumpukan Kaum Kiri". Struktur Data dan Algoritma Jaringan .
hlm. 38–42 . doi : 10.1137/1.9781611970265 ([Link]
65) . ISBN Telepon 978-0-89871-187-5.

20. Hayward, Ryan; McDiarmid, Colin (1991). "Analisis Kasus Rata-rata Pembentukan Heap
dengan Penyisipan Berulang" ([Link]
[Link]/__data/assets/pdf_file/0015/4173/[Link]) (PDF) . J. Algorithms .
12 : 126– 153. CiteSeerX [Link].7888 ([Link]
y?doi=[Link].7888) . doi : 10.1016/0196-6774(91)90027-v ([Link]
F0196-6774%2891%2990027-v) . Diarsipkan dari versi asli ([Link]
ata/assets/pdf_file/0015/4173/[Link]) (PDF) pada 2016-02-05 . Diakses
tanggal 2016-01-28 .

21. "Tumpukan Binomial | Brilliant Math & Science Wiki" ([Link]

p/) . [Link] . Diperoleh pada 2019-09-30 .

22. Brodal, Gerth Stølting; Okasaki, Chris (November 1996), "Antrian prioritas fungsional murni
yang optimal", Jurnal Pemrograman Fungsional , 6 (6): 839– 857, doi :
10.1017/s095679680000201x ([Link]

23. Okasaki, Chris (1998). "10.2. Abstraksi Struktural". Struktur Data Fungsional Murni (edisi ke-
1). hlm. 158– 162. ISBN nomor telepon 9780521631242.
24. Takaoka, Tadao (1999), Teori 2–3 Tumpukan ([Link]
10092/14769/[Link]) (PDF) , hal. 12

25. Iacono, John (2000), "Peningkatan batas atas untuk memasangkan tumpukan", Prosiding
Lokakarya Skandinavia ke-7 tentang Teori Algoritma ([Link]
[Link]) (PDF) , Catatan Kuliah dalam Ilmu Komputer, vol. 1851, Springer-Verlag, hlm.
63–77 , arXiv : 1110.4428 ([Link] , CiteSeerX [Link].7812
([Link] , doi : 10.1007/3-
540-44985-X_5 ([Link] , ISBN Nomor telepon 3-
540-67690-2

26. Fredman, Michael Lawrence (Juli 1999). "Tentang Efisiensi Pasangan Tumpukan dan
Struktur Data Terkait" ([Link]
f) (PDF) . Jurnal Asosiasi Mesin Komputasi . 46 (4): 473– 501. doi :
10.1145/320211.320214 ([Link] .

27. Pettie, Seth (2005). Menuju Analisis Akhir tentang Tumpukan Pasangan ([Link]
[Link]/~pettie/papers/[Link]) (PDF) . Prosiding Simposium Tahunan IEEE ke-46
tentang Dasar-dasar Ilmu Komputer, FOCS '05. hlm. 174–183 . CiteSeerX [Link].471 (h
ttps://[Link]/viewdoc/summary?doi=[Link].471) . doi :
10.1109/SFCS.2005.75 ([Link] . ISBN Nomor telepon
0-7695-2468-0.

28. Haeupler, Bernhard; Sen, Siddhartha; Tarjan, Robert E. (November 2011). "Tumpukan
pasangan peringkat" ([Link] (PDF) . SIAM J.
Komputasi . 40 (6): 1463– 1485. doi : 10.1137/100785351 ([Link]
785351) .

29. Fredman, Michael Lawrence ; Tarjan, Robert E. (Juli 1987). "Tumpukan Fibonacci dan
penggunaannya dalam algoritma optimasi jaringan yang lebih baik" ([Link]
~dbu/AlgorithmCourses/Lectures/[Link]) (PDF) . Jurnal Asosiasi
Mesin Komputasi . 34 (3): 596– 615. CiteSeerX [Link].8927 ([Link]
du/viewdoc/summary?doi=[Link].8927) . doi : 10.1145/28869.28874 ([Link]
g/10.1145%2F28869.28874) .

30. Brodal, Gerth Stølting ; Lagogiannis, George; Tarjan, Robert E. (2012). Tumpukan Fibonacci
yang ketat ([Link] (PDF) . Prosiding simposium
ke-44 tentang Teori Komputasi - STOC '12. hlm. 1177– 1184. CiteSeerX [Link].1740 (h
ttps://[Link]/viewdoc/summary?doi=[Link].1740) . doi :
10.1145/2213977.2214082 ([Link] .
ISBN Telepon: 978-1-4503-1245-5.
31. Brodal, Gerth S. (1996), "Antrian Prioritas Efisien Kasus Terburuk" ([Link]
rth/papers/[Link]) (PDF) , Prosiding Simposium Tahunan ACM-SIAM ke-7 tentang
Algoritma Diskrit , hlm. 52– 58

32. Goodrich, Michael T. ; Tamassia, Roberto (2004). "7.3.6. Konstruksi Heap Bottom-Up".
Struktur Data dan Algoritma dalam Java (edisi ke-3). hlm. 338–341 . ISBN Nomor telepon
0-471-46983-1.

Tautan eksternal

Struktur Data Terbuka - Bagian 10.1 - BinaryHeap: Pohon Biner Implisit ([Link]
[Link]/versions/edition-0.1e/ods-java/10_1_BinaryHeap_Implicit_Bi.html) , Pat Morin

Implementasi binary max heap di C ([Link] oleh Robin

Thomas

Implementasi min heap biner di C ([Link] oleh Robin

Thomas