Heap (İkili Yığın)
Son güncelleme
İkili yığın, en küçük (min-heap) veya en büyük (max-heap) değeri kökte tutan tam bir ikili ağaçtır. Bu görselleştirme bir min-heap'tir: her ebeveyn, çocuklarından küçük veya onlara eşittir. Bir değer eklemek için onu bir sonraki boş yuvaya koyar, ardından ebeveyninden küçük olduğu sürece onunla yer değiştirerek "yukarı süzersiniz", ta ki yığın özelliği yeniden sağlanana kadar. Yukarıdaki oynat düğmesine basarak her yeni değerin yerine doğru nasıl yükseldiğini izleyin.
Yığın tam bir ağaç olduğundan bir dizide sıkışık biçimde saklanır: i düğümünün çocukları 2i+1 ve 2i+2 konumundadır. Ekleme ve minimumu çıkarma O(log n)'dir (kökten yaprağa bir yol), minimuma bakmak ise O(1)'dir - bu tam olarak bir öncelik kuyruğunun ihtiyaç duyduğu şeydir.
Zaman ve alan karmaşıklığı
| İşlem | Karmaşıklık | Notlar |
|---|---|---|
| Min/maks'a bakma | O(1) | Her zaman köktür |
| Ekleme (push) | O(log n) | Bir yol boyunca yukarı süzme |
| Min/maks çıkarma | O(log n) | Bir yol boyunca aşağı süzme |
| Yığını inşa etme | O(n) | Hepsini bir kerede heapify |
| Alan | O(n) | Dizi tabanlı, işaretçi yok |
Adım adım (push)
| Adım | Ne olur |
|---|---|
| 1 | Yeni değeri sona ekle (bir sonraki boş yaprak). |
| 2 | Onu ebeveyniyle karşılaştır. |
| 3 | Daha küçükse (min-heap), yukarı doğru yer değiştir. |
| 4 | Ebeveyninden daha küçük olmayana veya köke ulaşana kadar tekrarla. |
Çözümlü örnek
[5, 3, 8, 1, 4] değerlerini birer birer ekleyerek bir min-heap inşa etme:
| Push | Süzme sonrası dizi | Eylem |
|---|---|---|
5 | [5] | İlk değer kök olur. |
3 | [3, 5] | 3 < ebeveyn 5, bu yüzden köke kadar yükselir. |
8 | [3, 5, 8] | 8 > ebeveyn 5, bu yüzden yaprak olarak kalır. |
1 | [1, 3, 8, 5] | 1 < ebeveyn 5, yer değiştirir; sonra 1 < ebeveyn 3, köke kadar yükselir. |
4 | [1, 3, 8, 5, 4] | 4 > ebeveyn 3, bu yüzden kalır; minimum 1 kökte kalır. |
Heap ne zaman kullanılır
| Şu durumda kullanın | Şu durumda kaçının |
|---|---|
| Değişen bir kümeden tekrar tekrar en küçük veya en büyük öğeye ihtiyacınız olduğunda. | Yalnızca uç değeri değil, keyfi değerleri aramanız gerektiğinde - bir BST veya hash kümesi kullanın. |
| Dijkstra, A* veya bir zamanlayıcı için öncelik kuyruğu uyguluyorsanız. | Verileri her zaman tam sıralı tutmanız gerektiğinde. |
Kompakt dizi düzeniyle O(log n) ekleme ve minimum çıkarma istediğinizde. | Belirli bir (kök olmayan) öğeyi hızlıca arama veya silme gerektiğinde. |
| Bir öğe akışını birleştirip önceliğe göre çekmeniz gerektiğinde. | Veri kümesi çok küçükse ve doğrusal tarama daha basit ve yeterince hızlıysa. |
Heap (Priority Queue) kodu
Python, JavaScript, Java, C++, C dillerinde temiz ve çalıştırılabilir bir Heap (Priority Queue) uygulaması. Bir dil seçin, kodu kopyalayın veya Coddy Playground'da hazır yüklenmiş olarak açın.
Python ile Heap (Priority Queue) kodu
Python
1class MinHeap:2 def __init__(self):3 self.data = []4
5 def push(self, value):6 # Append at the end, then bubble up to restore order7 self.data.append(value)8 i = len(self.data) - 19 while i > 0:10 parent = (i - 1) // 211 if self.data[parent] <= self.data[i]:12 break13 self.data[i], self.data[parent] = self.data[parent], self.data[i]14 i = parent15
16 def pop(self):17 # Move the last leaf to the root, then sift it down18 top = self.data[0]19 last = self.data.pop()20 if self.data:21 self.data[0] = last22 self._sift_down(0)23 return top24
25 def _sift_down(self, i):26 n = len(self.data)27 while True:28 smallest = i29 left, right = 2 * i + 1, 2 * i + 230 if left < n and self.data[left] < self.data[smallest]:31 smallest = left32 if right < n and self.data[right] < self.data[smallest]:33 smallest = right34 if smallest == i:35 return36 self.data[i], self.data[smallest] = self.data[smallest], self.data[i]37 i = smallest38
39
40heap = MinHeap()41for value in [5, 3, 8, 1, 9, 2]:42 heap.push(value)43
44print("Heap array: ", heap.data)45print("Popped in order:", [heap.pop() for _ in range(6)])JavaScript ile Heap (Priority Queue) kodu
JavaScript
1class MinHeap {2 constructor() {3 this.items = [];4 }5
6 push(value) {7 this.items.push(value);8 // Bubble the new value up while it is smaller than its parent9 let i = this.items.length - 1;10 while (i > 0) {11 const parent = Math.floor((i - 1) / 2);12 if (this.items[parent] <= this.items[i]) break;13 [this.items[parent], this.items[i]] = [this.items[i], this.items[parent]];14 i = parent;15 }16 }17
18 pop() {19 const top = this.items[0];20 const last = this.items.pop();21 if (this.items.length > 0) {22 this.items[0] = last;23 this.sinkDown(0);24 }25 return top;26 }27
28 sinkDown(i) {29 const n = this.items.length;30 while (true) {31 let smallest = i;32 const left = 2 * i + 1;33 const right = 2 * i + 2;34 if (left < n && this.items[left] < this.items[smallest]) smallest = left;35 if (right < n && this.items[right] < this.items[smallest]) smallest = right;36 if (smallest === i) return;37 [this.items[i], this.items[smallest]] = [this.items[smallest], this.items[i]];38 i = smallest;39 }40 }41}42
43const heap = new MinHeap();44for (const value of [5, 2, 9, 1, 7, 3]) heap.push(value);45const sorted = [];46while (heap.items.length > 0) sorted.push(heap.pop());47console.log("Popped in order:", sorted.join(" "));Java ile Heap (Priority Queue) kodu
Java
1public class Main {2 static int[] heap = new int[32];3 static int size = 0;4
5 static void push(int value) {6 heap[size] = value;7 int i = size++;8 // Sift up while smaller than the parent9 while (i > 0 && heap[(i - 1) / 2] > heap[i]) {10 swap(i, (i - 1) / 2);11 i = (i - 1) / 2;12 }13 }14
15 static int pop() {16 int min = heap[0];17 heap[0] = heap[--size];18 int i = 0;19 // Sift down: swap with the smaller child until in place20 while (true) {21 int smallest = i, l = 2 * i + 1, r = 2 * i + 2;22 if (l < size && heap[l] < heap[smallest]) smallest = l;23 if (r < size && heap[r] < heap[smallest]) smallest = r;24 if (smallest == i) break;25 swap(i, smallest);26 i = smallest;27 }28 return min;29 }30
31 static void swap(int a, int b) {32 int tmp = heap[a];33 heap[a] = heap[b];34 heap[b] = tmp;35 }36
37 public static void main(String[] args) {38 int[] values = {9, 4, 7, 1, 8, 2};39 for (int v : values) push(v);40 System.out.print("Popped in order:");41 while (size > 0) System.out.print(" " + pop());42 System.out.println();43 }44}C++ ile Heap (Priority Queue) kodu
C++
1#include <iostream>2#include <utility>3#include <vector>4
5struct MinHeap {6 std::vector<int> data;7
8 void push(int value) {9 data.push_back(value);10 // Sift up until the parent is no larger11 size_t i = data.size() - 1;12 while (i > 0) {13 size_t parent = (i - 1) / 2;14 if (data[parent] <= data[i]) break;15 std::swap(data[parent], data[i]);16 i = parent;17 }18 }19
20 int pop() {21 int top = data[0];22 data[0] = data.back();23 data.pop_back();24 // Sift down: swap with the smaller child25 size_t i = 0;26 while (true) {27 size_t l = 2 * i + 1, r = 2 * i + 2, smallest = i;28 if (l < data.size() && data[l] < data[smallest]) smallest = l;29 if (r < data.size() && data[r] < data[smallest]) smallest = r;30 if (smallest == i) break;31 std::swap(data[i], data[smallest]);32 i = smallest;33 }34 return top;35 }36
37 int peek() const { return data[0]; }38 bool empty() const { return data.empty(); }39};40
41int main() {42 MinHeap heap;43 for (int value : {5, 3, 8, 1, 9, 2}) heap.push(value);44 std::cout << "Min: " << heap.peek() << "\n";45 std::cout << "Popped in order: ";46 while (!heap.empty()) std::cout << heap.pop() << " ";47 std::cout << "\n";48 return 0;49}C ile Heap (Priority Queue) kodu
C
1#include <stdio.h>2
3#define CAP 644
5int heap[CAP];6int heapSize = 0;7
8void push(int value) {9 // Sift up until the parent is no larger10 int i = heapSize++;11 heap[i] = value;12 while (i > 0) {13 int parent = (i - 1) / 2;14 if (heap[parent] <= heap[i]) break;15 int tmp = heap[parent];16 heap[parent] = heap[i];17 heap[i] = tmp;18 i = parent;19 }20}21
22int pop(void) {23 int top = heap[0];24 heap[0] = heap[--heapSize];25 // Sift down: swap with the smaller child26 int i = 0;27 while (1) {28 int l = 2 * i + 1, r = 2 * i + 2, smallest = i;29 if (l < heapSize && heap[l] < heap[smallest]) smallest = l;30 if (r < heapSize && heap[r] < heap[smallest]) smallest = r;31 if (smallest == i) break;32 int tmp = heap[i];33 heap[i] = heap[smallest];34 heap[smallest] = tmp;35 i = smallest;36 }37 return top;38}39
40int main(void) {41 int values[] = {5, 3, 8, 1, 9, 2};42 for (int i = 0; i < 6; i++) push(values[i]);43 printf("Min: %d\n", heap[0]);44 printf("Popped in order: ");45 while (heapSize > 0) printf("%d ", pop());46 printf("\n");47 return 0;48}Heap SSS
Heap ne için kullanılır?
Heap'ler, Dijkstra'nın en kısa yol algoritmasını, görev zamanlayıcılarını ve olay simülasyonlarını çalıştıran öncelik kuyruklarını uygular. Ayrıca heapsort'un arkasındaki motordur. Değişen bir kümeden tekrar tekrar en küçük veya en büyük öğeye ihtiyaç duyduğunuzda araç bir heap'tir.
Heap ile ikili arama ağacı arasındaki fark nedir?
Her ikisi de ikili ağaçtır, ancak bir BST tam bir soldan sağa sıralı düzen tutar (sıralı aramayı mümkün kılar), oysa bir heap yalnızca ebeveyn-çocuk ilişkisini garanti eder (kökte min veya maks). Bir heap uç değere O(1) erişim verir; bir BST herhangi bir değere O(log n) arama verir.
Bir heap neden dizide saklanır?
Bir heap her zaman tam bir ikili ağaç olduğundan, düğümleri dizi indekslerine kusursuzca eşlenir:
i indeksinin çocukları 2i+1 ve 2i+2'de, ebeveyni (i-1)/2'dedir. Bu, çocuk işaretçilerini saklamayı önler ve mükemmel önbellek performansı sağlar.Bir heap, sıralı bir diziyle aynı mıdır?
Hayır. Bir heap yalnızca her ebeveynin çocuklarından küçük (min-heap) veya büyük (max-heap) olduğunu garanti eder, bu yüzden kardeşler ve kuzenler belirli bir sırada değildir. Sıralı bir dizi tam olarak sıralıdır ancak eklemesi
O(n) maliyetlidir, oysa bir heap O(log n)'de ekler ve yine de uç değere anında erişim verir.Bir diziyi sadece sıralamak yerine ne zaman heap kullanmalıyım?
Veriler sürekli değişiyorsa ve yalnızca mevcut minimum veya maksimuma ihtiyacınız varsa bir heap'e yönelin - ekleme ve çıkarma her biri
O(log n)'dir, tüm diziyi yeniden sıralamaya karşı. Statik bir veri kümeniz varsa ve tüm öğeleri sırayla istiyorsanız, tek bir O(n log n) sıralama daha basit ve genellikle daha hızlıdır.n öğeden bir heap inşa etmek O(n log n) sürer mi?
Hepsini bir kerede inşa ederseniz sürmez.
n öğeyi tek tek eklemek O(n log n)'dir, ancak son ebeveynden köke doğru aşağı süzen aşağıdan yukarıya heapify toplamda O(n) çalışır, çünkü çoğu düğüm en alta yakındır ve yalnızca kısa bir mesafe aşağı süzülür.İlgili kaynaklar
Daha fazla görselleştirme
