Masalah tumpukan d-ary dari CLRS

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 $A[a_1 .. a_n]$

$\qquad \begin{align} \text{root} &: a_1\\ \text{level 1} &: a_{2} \dots a_{2+d-1}\\ \text{level 2} &: a_{2+d} \dots a_{2+d+d^2-1}\\ &\vdots\\ \text{level k} &: a_{2+\sum\limits_{i=1}^{k-1}d^i} \dots a_{2+\sum\limits_{i=1}^{k}d^i-1} \end{align}$

→ Notasi saya agak canggih. Apakah ada yang lebih sederhana?
Biarkan h menunjukkan ketinggian tumpukan d -ary.

Misalkan heap adalah pohon d -ary lengkap
$1 + d + d^{2} + . . + d^{h} = n \frac{d^{h + 1} - 1}{d - 1} = n h = l o g_{d} [n d - 1 + 1] - 1$ $1+d+d^2+..+d^h=n\\ \dfrac{d^{h+1}-1}{d-1}=n\\ h=log_d[n{d-1}+1] - 1$
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:
  
  $T_{M} = d (c_{8} * d + (c_{9} + . . + c_{1} 3) * d + c_{1} 4 * d)$ $T_M = d(c_8*d + (c_9+..+c_13)*d +c_14*d)$ mana menunjukkan biaya baris ke- i di atas. $c_i$
- EXTRACT-MAX:
  $T_{E} = (c_{1} + . . + c_{7}) + T_{M} \leq C * d * h = C * d * (l o g_{d} [n (d - 1) + 1] - 1) = O (d l o g_{d} [n (d - 1)])$ $T_E = (c_1+..+c_7) + T_M \leq C*d*h\\ = C*d*(log_d[n(d-1)+1] - 1)\\ = O(dlog_d[n(d-1)])$
→ Apakah ini solusi yang efisien? Atau ada sesuatu yang salah dalam solusi saya?

data-structures time-complexity runtime-analysis lucasKo
sumber

Saya pikir ada sedikit kesalahan dalam pertanyaan serta penjelasan: Ketinggian tumpukan d-ary datang ke h = (log [nd - n + 1]) - 1 // Perhatikan "-n" dan tidak "-1" dan bukan h = (log [nd−1+1])− 1Jadi 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 .

Surabhi Raje

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.

$\text{d-ary-parent}({\it i}) \\ \ \ \ \ {\bf return}\ \lfloor (i-2)/d + 1 \rfloor$

$\text{d-ary-child}(i, j) \\ \ \ \ \ {\bf return}\ d(i-1)+j+1$

Jelas . Anda dapat memverifikasi fungsi-fungsi yang memeriksa $1 \le j \le d$ $\text{d-ary-parent}(\text{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 = log_d(n\,d-1+1) - 1$ $\log_d(n\,d) - 1 = \log_d(n) + \log_d(d) - 1 = \log_d(n) + 1 - 1 = \log_d(n)$ $\Theta(\log_d(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$ $\Theta$
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$ $\text{d-ary-parent}$ $\text{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: $\text{EXTRACT-MAX}$ $\text{MAX-HEAPIFY}$ $O(d\ \log_d(n(d-1)))$

$O(d\ \log_d(n(d-1))) = O(d(\log_d(n) + \log(d-1))) = O(d\ log_d(n) + d\ \log_d(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 \ll n$ $d \log_d(d-1)$ $O(d\log_d(n))$ $\text{MAX-HEAPIFY}$ $O$ $\Theta$
Buku CLRS sudah menyediakan prosedur INSERT. Yang terlihat seperti ini:

$\text{INSERT}(A, key)\\ \ \ \ \ A.heap\_size = A.heap\_size + 1 \\ \ \ \ \ A[A.heap\_size] = -\infty\\ \ \ \ \ \text{INCREASE-KEY}(A, A.heap\_size, key)$

Itu bisa dibuktikan dengan mudah tetapi akal sehat menyatakan bahwa kompleksitas waktunya adalah . Itu karena tumpukan mungkin dilalui sampai ke akar. $O(\log_d(n))$
Sama seperti INSERT, INCREASE-KEY juga didefinisikan dalam buku teks sebagai:

$\text{INCREASE-KEY}(A, i, key)\\ \ \ \ \ {\bf if}\ key < A[i]\\ \ \ \ \ \ \ \ \ {\bf error} \text{"new key is smaller then current"}\\ \ \ \ \ A[i] = key\\ \ \ \ \ {\bf while}\ i > 1\ and\ A[i] > A[\text{d-ary-parent}(i)]\\ \ \ \ \ \ \ \ \ A[i] \leftrightarrow A[\text{d-ary-parent(i)}]\\ \ \ \ \ \ \ \ \ i = \text{d-ary-parent(i)}$

Kompleksitas jelas (lihat poin sebelumnya). $O(\log_d(n))$

Bartosz Przybylski
sumber

Terima kasih! Bagaimana dengan implementasi INCREASE-KEY dan INSERT? Saya mencoba untuk menulisnya, tetapi itu memberi panggilan rekursif MAX-HEAPIFY dua kali. Apakah ada solusi yang lebih baik? Saya menemukan sedikit informasi di web dan wiki

lucasKo

Apakah sisa latihan itu? Jika demikian silakan perbarui pertanyaan Anda dan saya akan dengan senang hati menjawab tema.

Bartosz Przybylski

Saya menempatkan pertanyaan itu di pos yang diedit.

lucasKo

Penerapan kembali prosedur INSERT? Maksud Anda, itu tidak harus memanggil prosedur yang menyesuaikan urutan di dalam tumpukan, setelah memasukkan elemen baru? Saya tidak mengerti ...

lucasKo

Deskripsi itu agak disayangkan, lihat suntingan untuk klarifikasi.

Bartosz Przybylski

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)

h = l o g_{d} [n d - 1 + 1] - 1

$h=log_d[n{d-1}+1] - 1$

1 + d + d^{2} + . . + d^{h} = n \frac{d^{h + 1} - 1}{d - 1} = n h = l o g_{d} [n (d - 1) + 1] - 1

$1+d+d^2+..+d^h=n\\ \dfrac{d^{h+1}-1}{d-1}=n\\ h=log_d[n(d-1)+1] - 1$

h = Θ (\log_{d} (n))

$h=\Theta(\log_d(n))$

Ali Jazib Mahmood
sumber

-1

Jawaban untuk pertanyaan kedua adalah h = log _d (n (d-1) + 1) - 1 Jadi, h = log _d (nd - n + 1) - 1

user55463
sumber

Mengapa ini jawabannya? Formula tanpa penjelasan tidak benar-benar membantu siapa pun.

David Richerby