Kopiec (kopiec binarny)
Ostatnia aktualizacja
Kopiec binarny to zupełne drzewo binarne, które trzyma najmniejszą (kopiec min) lub największą (kopiec max) wartość w korzeniu. Ta wizualizacja pokazuje kopiec min: każdy rodzic jest mniejszy lub równy swoim dzieciom. Aby dodać wartość, dopisujesz ją w następnym wolnym miejscu, a potem "przesiewasz ją w górę", zamieniając z rodzicem, dopóki jest od niego mniejsza, aż własność kopca znów będzie spełniona. Kliknij odtwarzanie powyżej i zobacz, jak każda nowa wartość wypływa na swoje miejsce.
Ponieważ kopiec jest drzewem zupełnym, przechowuje się go zwięźle w tablicy: dzieci węzła i są pod indeksami 2i+1 i 2i+2. Wstawianie i usuwanie minimum kosztują O(log n) (jedna ścieżka od korzenia do liścia), a podgląd minimum O(1), czyli dokładnie to, czego potrzebuje kolejka priorytetowa.
Złożoność czasowa i pamięciowa
| Operacja | Złożoność | Uwagi |
|---|---|---|
| Podgląd min/max | O(1) | To zawsze korzeń |
| Wstawianie (push) | O(log n) | Przesiewanie w górę jednej ścieżki |
| Usuwanie min/max | O(log n) | Przesiewanie w dół jednej ścieżki |
| Budowa kopca | O(n) | Kopcowanie wszystkiego naraz |
| Pamięć | O(n) | Oparty na tablicy, bez wskaźników |
Krok po kroku (push)
| Krok | Co się dzieje |
|---|---|
| 1 | Dopisz nową wartość na końcu (następny wolny liść). |
| 2 | Porównaj ją z rodzicem. |
| 3 | Jeśli jest mniejsza (kopiec min), zamień ją w górę. |
| 4 | Powtarzaj, dopóki nie przestanie być mniejsza od rodzica albo nie dotrze do korzenia. |
Przykład krok po kroku
Budowanie kopca min przez dodawanie [5, 3, 8, 1, 4] po jednej wartości:
| Push | Tablica po przesianiu w górę | Działanie |
|---|---|---|
5 | [5] | Pierwsza wartość zostaje korzeniem. |
3 | [3, 5] | 3 < rodzic 5, więc zamień ją w górę do korzenia. |
8 | [3, 5, 8] | 8 > rodzic 5, więc zostaje liściem. |
1 | [1, 3, 8, 5] | 1 < rodzic 5, zamiana; potem 1 < rodzic 3, zamiana aż do korzenia. |
4 | [1, 3, 8, 5, 4] | 4 > rodzic 3, więc zostaje; minimum 1 pozostaje w korzeniu. |
Kiedy używać kopca
| Używaj, gdy | Unikaj, gdy |
|---|---|
| Wielokrotnie potrzebujesz najmniejszego lub największego elementu ze zmieniającego się zbioru. | Musisz wyszukiwać dowolne wartości, a nie tylko skrajne: użyj drzewa BST lub zbioru haszującego. |
| Implementujesz kolejkę priorytetową dla algorytmu Dijkstry, A* lub planisty zadań. | Potrzebujesz danych przez cały czas w pełni posortowanych. |
Chcesz wstawiania i usuwania minimum w O(log n) przy zwięzłym układzie w tablicy. | Potrzebujesz szybkiego wyszukiwania lub usuwania konkretnego elementu (innego niż korzeń). |
| Musisz scalać strumień elementów i wyciągać je według priorytetu. | Zbiór danych jest malutki, a liniowe przeglądanie jest prostsze i wystarczająco szybkie. |
Heap (Priority Queue): kod
Przejrzysta, gotowa do uruchomienia implementacja algorytmu Heap (Priority Queue) w językach: Python, JavaScript, Java, C++, C. Wybierz język, skopiuj kod albo otwórz go od razu w edytorze online Coddy.
Heap (Priority Queue): kod (Python)
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)])Heap (Priority Queue): kod (JavaScript)
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(" "));Heap (Priority Queue): kod (Java)
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}Heap (Priority Queue): kod (C++)
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}Heap (Priority Queue): kod (C)
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}Kopiec: najczęstsze pytania
Do czego służy kopiec?
Kopce implementują kolejki priorytetowe, na których opiera się algorytm najkrótszej ścieżki Dijkstry, planiści zadań i symulacje zdarzeń. Są też silnikiem sortowania przez kopcowanie. Zawsze, gdy wielokrotnie potrzebujesz najmniejszego lub największego elementu ze zmieniającego się zbioru, kopiec jest właściwym narzędziem.
Czym różni się kopiec od binarnego drzewa poszukiwań?
Oba są drzewami binarnymi, ale drzewo BST utrzymuje pełny porządek od lewej do prawej (co umożliwia wyszukiwanie w porządku), a kopiec gwarantuje tylko relację rodzic-dziecko (min lub max w korzeniu). Kopiec daje dostęp do wartości skrajnej w O(1); drzewo BST daje wyszukiwanie dowolnej wartości w O(log n).
Dlaczego kopiec przechowuje się w tablicy?
Ponieważ kopiec jest zawsze zupełnym drzewem binarnym, jego węzły idealnie odwzorowują się na indeksy tablicy: dzieci indeksu
i są pod 2i+1 i 2i+2, a rodzic pod (i-1)/2. Dzięki temu nie trzeba przechowywać wskaźników na dzieci, a wydajność pamięci podręcznej jest świetna.Czy kopiec to to samo co posortowana tablica?
Nie. Kopiec gwarantuje tylko, że każdy rodzic jest mniejszy (kopiec min) lub większy (kopiec max) od swoich dzieci, więc rodzeństwo i kuzyni nie mają określonego porządku. Posortowana tablica jest w pełni uporządkowana, ale wstawianie do niej kosztuje
O(n), a kopiec wstawia w O(log n) i nadal daje natychmiastowy dostęp do wartości skrajnej.Kiedy użyć kopca zamiast po prostu posortować tablicę?
Sięgnij po kopiec, gdy dane ciągle się zmieniają, a potrzebujesz tylko bieżącego minimum lub maksimum: wstawienie i zdjęcie kosztują po
O(log n), zamiast ponownego sortowania całej tablicy. Jeśli zbiór danych jest statyczny i chcesz mieć wszystkie elementy w kolejności, jedno sortowanie O(n log n) jest prostsze i często szybsze.Czy zbudowanie kopca z n elementów zajmuje O(n log n)?
Nie, jeśli budujesz go naraz. Wstawianie
n elementów po kolei kosztuje O(n log n), ale oddolne heapify, które przesiewa w dół od ostatniego rodzica do korzenia, działa łącznie w O(n), bo większość węzłów leży blisko dołu i przesiewa się tylko na krótką odległość.Powiązane materiały
Więcej wizualizacji
