Saya bingung saat memecahkan masalah berikut (pertanyaan 1-3).
Pertanyaan
Sebuah d tumpukan -ary seperti tumpukan biner, tetapi (dengan satu pengecualian mungkin) node non-daun memiliki d anak bukannya 2 anak-anak.
Bagaimana Anda mewakili tumpukan d -ary dalam array?
Berapa tinggi dari d tumpukan -ary dari n elemen dalam hal n dan d ?
Berikan implementasi yang efisien dari EXTRACT-MAX di d -ary max-heap. Menganalisis waktu berjalannya dalam hal d dan n .
Berikan implementasi yang efisien dari INSERT di d -ary max-heap. Menganalisis waktu berjalannya dalam hal d dan n .
Berikan implementasi INCREASE-KEY ( A , i , k ) yang efisien , yang menandai kesalahan jika k <A [i] = k dan kemudian memperbarui struktur tumpukan matriks d -ary secara tepat. Menganalisis waktu berjalannya dalam hal d dan n .
Solusi saya
Berikan array
→ Notasi saya agak canggih. Apakah ada yang lebih sederhana?
Biarkan h menunjukkan ketinggian tumpukan d -ary.
Misalkan heap adalah pohon d -ary lengkap
Ini implementasi saya:
EXTRACT-MAX(A) 1 if A.heapsize < 1 2 error "heap underflow" 3 max = A[1] 4 A[1] = A[A.heapsize] 5 A.heap-size = A.heap-size - 1 6 MAX-HEAPIFY(A, 1) 7 return max MAX-HEAPIFY(A, i) 1 assign depthk-children to AUX[1..d] 2 for k=1 to d 3 compare A[i] with AUX[k] 4 if A[i] <= AUX[k] 5 exchange A[i] with AUX[k] 6 k = largest 7 assign AUX[1..d] back to A[depthk-children] 8 if largest != i 9 MAX-HEAPIFY(A, (2+(1+d+d^2+..+d^{k-1})+(largest-1) )
Waktu berjalan MAX-HEAPIFY:
mana menunjukkan biaya baris ke- i di atas.EXTRACT-MAX:
→ Apakah ini solusi yang efisien? Atau ada sesuatu yang salah dalam solusi saya?
h = (log [nd−1+1])− 1
Jadi kami penjelasan di atas untuk ketinggian tidak akan berlaku. h = log [nd − 1 + 1] −1 = log [nd] -1 = log [n] Meskipun demikian, ketinggian pohon ditulis sebagaiΘ(log(n)).
Catatan: log selalu ke pangkalan d untuk tumpukan d-ary .Jawaban:
Solusi Anda valid dan mengikuti definisi d -ary heap. Tetapi ketika Anda menunjukkan notasi Anda agak canggih.
Anda mungkin menggunakan dua fungsi berikut untuk mengambil induk i elemen -th dan j anak -th i elemen th.
Jelas . Anda dapat memverifikasi fungsi-fungsi yang memeriksa1≤j≤d d-ary-parent(d-ary-child(i,j))=i
Juga mudah untuk melihat adalah bahwa tumpukan biner adalah jenis khusus dari tumpukan -ary mana , jika Anda mengganti dengan , maka Anda akan melihat bahwa mereka cocok fungsi INDUK, KIRI dan KANAN disebutkan dalam buku.d d=2 d 2
Jika saya memahami jawaban Anda dengan benar, Anda menggunakan deret ukur geometris . Dalam kasus Anda, Anda bisa pergi , yang jelas , yang sebenarnya merupakan solusi yang valid dan benar. Tetapi hanya demi menangani fluktuasi konstan, Anda mungkin ingin menulis .h=logd(nd−1+1)−1 logd(nd)−1=logd(n)+logd(d)−1=logd(n)+1−1=logd(n) Θ(logd(n))
Alasan untuk ini adalah bahwa beberapa tumpukan mungkin tidak seimbang, sehingga lintasan terpanjang dan lintasan terpendeknya bervariasi oleh beberapa konstanta , dengan menggunakan notasi Anda menghilangkan masalah ini.c Θ
Anda tidak perlu mengimplementasikan kembali prosedur yang diberikan dalam buku teks, tetapi Anda harus sedikit mengubahnya, misalnya menetapkan semua anak ke tabel menggunakan dan fungsi.AUX d-ary-parent d-ary-child
Karena tidak diubah, itu tergantung pada waktu berjalan dari . Dalam analisis Anda, Anda sekarang harus menggunakan waktu terburuk yang sebanding dengan tinggi badan dan jumlah anak yang harus diperiksa oleh setiap simpul (paling banyak adalah d ). Sekali lagi analisis Anda sangat tepat, pada akhirnya Anda mendapatkan , yang dapat diubah menjadi:EXTRACT-MAX MAX-HEAPIFY O(d logd(n(d−1)))
Untuk alasan praktis kita selalu dapat mengasumsikan bahwa , sehingga kita dapat kehilangan bagian dari notasi O , maka kita akan mendapatkan . Yang juga merupakan solusi yang valid. Tetapi tidak mengherankan Anda juga dapat menganalisis fungsi waktu berjalan menggunakan teorema Master , yang akan menunjukkan bahwa tidak hanya tetapi bahkan .d≪n dlogd(d−1) O(dlogd(n)) MAX-HEAPIFY O Θ
Buku CLRS sudah menyediakan prosedur INSERT. Yang terlihat seperti ini:
Itu bisa dibuktikan dengan mudah tetapi akal sehat menyatakan bahwa kompleksitas waktunya adalah . Itu karena tumpukan mungkin dilalui sampai ke akar.O(logd(n))
Sama seperti INSERT, INCREASE-KEY juga didefinisikan dalam buku teks sebagai:
Kompleksitas jelas (lihat poin sebelumnya).O(logd(n))
sumber
Ini bukan jawaban yang lengkap. bagian b) solusinya bukan Its seperti yang ditunjukkan oleh pengguna 55463 (karena dia tidak dapat berkomentar, tetapi menjawab), tetapi diturunkan karena kurangnya penjelasan . Jawaban terangkat juga salah mengatasinya. Jawabannya tetap Sumber: Soal 2-2. Analisis tumpukan tumpukan, bagian b)
sumber
Jawaban untuk pertanyaan kedua adalah h = log d (n (d-1) + 1) - 1 Jadi, h = log d (nd - n + 1) - 1
sumber