Dalam banyak diskusi tentang tumpukan biner, biasanya hanya kunci-menurun terdaftar sebagai operasi yang didukung untuk tumpukan-min. Sebagai contoh, CLR bab 6.1 dan halaman wikipedia ini . Mengapa tidak menambah kunci yang biasanya terdaftar untuk min-heap? Saya membayangkan adalah mungkin untuk melakukan itu dalam O (tinggi) dengan secara iteratif menukar elemen yang meningkat (x) dengan minimum anak-anaknya, sampai tidak ada anak-anaknya yang lebih besar dari x.
misalnya
IncreaseKey(int pos, int newValue)
{
heap[pos] = newValue;
while(left(pos) < heap.Length)
{
int smallest = left(pos);
if(heap[right(pos)] < heap[left(pos)])
smallest = right(pos);
if(heap[pos] < heap[smallest])
{
swap(smallest, pos);
pos= smallest;
}
else return;
}
}
Apakah hal di atas benar? Jika tidak, mengapa? Jika ya, mengapa tidak menambahkan kunci terdaftar untuk min-heap?
algorithms
data-structures
heaps
priority-queues
GatotPujo
sumber
sumber
Jawaban:
Algoritma yang Anda sarankan hanyalah heapify. Dan memang - jika Anda meningkatkan nilai elemen dalam min-heap, dan kemudian heapify subtree-nya, maka Anda akan berakhir dengan min-heap legal.
sumber
Alasan bahwa operasi Anda tidak terdaftar, adalah bahwa seseorang tidak hanya tertarik pada semua operasi yang dapat dengan mudah diimplementasikan menggunakan struktur data tertentu, tetapi sebaliknya. Dengan serangkaian operasi, cara apa yang paling efisien (dalam hal ruang dan waktu) untuk mengimplementasikan operasi ini. (Tapi saya menambahkan lebih banyak ke ini nanti)
Biner tumpukan menerapkan antrian prioritas struktur data abstrak, yang meminta operasi is_empty, add_element (kunci dengan prioritasnya), find_min, dan delete_min. Antrian yang lebih maju juga memungkinkan seseorang untuk mengurangi prioritas kunci (dalam min_heap) atau bahkan meningkatkannya. Bahkan, Anda telah memberikan implementasi.
Dua komentar. Operasi Anda digunakan dalam fungsi heapify, yang secara efisien membangun heap dari array. Dalam heapify operasi Anda diulangi (mulai dari kunci terakhir).
Kemudian, yang paling penting, kode Anda menggunakan posisi node. Untuk antrian prioritas struktur data murni yang curang. Struktur data itu meminta untuk melakukan operasi tertentu yang diberi kunci. Jadi untuk mengurangi atau menambah prioritas suatu elemen, Anda harus terlebih dahulu menemukannya. Saya pikir itu adalah alasan utama tidak terdaftar.
sumber
Saya pikir hal pertama yang perlu dipertimbangkan adalah operasi apa yang didukung?
Apakah "memasukkan nilai dengan kunci tetap tertentu" (mis. Untuk kunci yang diambil dari ranah integer, menyisipkan dengan kunci = 3) sesuai dengan operasi yang didukung untuk tumpukan min?
Tidak, karena operasi itu dapat diterapkan secara sepele dengan operasi yang didukung lebih umum. Demikian juga, memasukkan 2 elemen sekaligus dapat dilakukan dengan
insertoperasi yang ada .Di sisi lain,
insertoperasi tidak dapat ditentukan selain dengan mengekspos detail implementasi. Ini hampir sama untuk operasi yang terdaftar di halaman wikipedia,heapifykecuali, yang mungkin dapat diimplementasikan dengan urutaninsert.Dengan kata lain, ada operasi dasar yang disediakan pada tipe, yang terikat erat dengan detail implementasi agar mereka dapat bekerja dengan baik, dan ada operasi lain, yang tidak mematuhi aturan itu, dan dengan demikian dapat diimplementasikan sebagai kombinasi dari yang kanonik.
Dengan mempertimbangkan definisi itu, apakah Anda berpikir bahwa peningkatan kunci dapat diimplementasikan dengan operasi lain yang didukung secara eksklusif, tanpa kehilangan kinerja? Jika demikian, maka itu bukan operasi yang didukung oleh definisi di atas, jika tidak, Anda mungkin benar.
Bisa dibilang, definisi operasi yang didukung yang saya berikan adalah milik saya, sejauh yang saya tahu. Itu tidak formal, dan karenanya harus didiskusikan (walaupun tampaknya cukup jelas bagi saya). Namun, saya akan senang jika seseorang dapat memberikan sumber yang dengan jelas dan jelas mendefinisikan apa operasi yang didukung untuk tipe data, atau setidaknya mendefinisikannya dalam istilah yang lebih baik daripada milik saya (apakah definisi yang diberikan dalam CLR? Saya tidak memiliki salinan ).
Poin kedua saya adalah bagaimana kita mendefinisikan antrian prioritas (yang merupakan raison d'être dari tumpukan biner). Apakah
increase_keyoperasi yang diperlukan untuk tipe data itu, yaitu untuk penggunaan yang tepat?Seperti yang Anda lihat sudut saya adalah tentang definisi. Saya tidak benar-benar memberikan jawaban untuk pertanyaan Anda, hanya beberapa petunjuk, jadi penyempurnaan disambut.
sumber