Fungsi potensi biner heap extract maks O (1)

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)$

Saya tahu bahwa fungsi penyisipan harus "membayar" lebih banyak untuk mengurangi biaya ekstraksi, dan ini harus berkaitan dengan ketinggian tumpukan (jika memberikan ketinggian tumpukan jika masukkan menjadi atau )$\lfloor \log(n) \rfloor$$2\log(n)$$\sum_{k=1}^n 2\log(k)$

Coba yang berikut ini:

Berat dari unsur i dalam tumpukan H adalah kedalaman di pohon biner. Jadi elemen di root memiliki bobot nol, kedua anaknya memiliki bobot 1 dan seterusnya. Anda mendefinisikan sebagai fungsi potensial$w_i$$i$$H$

Sekarang mari kita menganalisis operasi tumpukan. Untuk memasukkan Anda menambahkan elemen baru tambahkan kedalaman paling banyak log ( n ) . Ini meningkatkan potensi sebesar 2 d , dan dapat dilakukan dalam O ( 1 ) waktu. Kemudian Anda "menggelembungkan" elemen tumpukan baru untuk memastikan properti tumpukan. Ini membutuhkan waktu O ( log n ) dan membiarkan Φ ( H ) tidak berubah. Jadi biaya untuk memasukkan adalah O ( log ( n ) + Δ ( Φ $d$$\log(n)$$2d$$O(1)$$O(\log n)$$\Phi(H)$ .$O(\log(n)+\Delta(\Phi(H)))=O(\log n)$

Sekarang pertimbangkan extractMin . Anda mengambil root dan menggantinya dengan elemen terakhir di heap. Ini mengurangi potensi sebesar , sehingga Anda dapat memperbaiki properti tumpukan, dan oleh karena itu biaya yang diamortisasi sekarang adalah O ( 1 ) .$2\log(n)$$O(1)$

Jika Anda memiliki pertanyaan umum untuk fungsi potensial, Anda harus mengajukan ini sebagai pertanyaan yang berbeda.