0Pricing
Coding Interview Prep · Lekcja

Własność kopca i reprezentacja tablicowa

Zrozumieją Państwo strukturę pełnego drzewa binarnego przechowywaną jako tablica, wyprowadzą wzory indeksów rodzica i dzieci oraz zwizualizują operacje sift-up i sift-down.

Własność kopca i reprezentacja tablicowa to bezpłatna lekcja Coding Interview Prep na CoddyKit. To lekcja 1 z 4. Możesz przeczytać całą lekcję poniżej za darmo — a potem ćwiczyć ją interaktywnie w przeglądarce z wbudowanym edytorem kodu i tutorem AI dostępnym 24/7. To część ścieżki edukacyjnej Coding Interview Prep, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs Coding Interview Prep zawiera 4 lekcji w sumie.

Co to jest kopiec?

Kopiec to wyspecjalizowane zupełne drzewo binarne spełniające własność kopca: w kopcu minimalnym każdy rodzic jest mniejszy lub równy swoim dzieciom, a w kopcu maksymalnym każdy rodzic jest większy lub równy swoim dzieciom. Własność ta gwarantuje, że element minimalny lub maksymalny zawsze znajduje się w korzeniu, umożliwiając dostęp do elementu skrajnego w czasie O(1). Kopce są strukturą danych stanowiącą podstawę kolejek priorytetowych.

# Min-heap example:
#         1
#        / \
#       3   2
#      / \ / \
#     7  4 5  6
# Every parent <= its children
# Root (1) is always the minimum

# Max-heap example:
#         9
#        / \
#       7   8
#      / \ / \
#     3  4 5  6
# Every parent >= its children
# Root (9) is always the maximum
print('Heap property: parent dominates all descendants')

Struktura zupełnego drzewa binarnego

Kopiec jest przechowywany jako zupełne drzewo binarne — wszystkie poziomy są całkowicie wypełnione, z wyjątkiem ewentualnie ostatniego, który jest wypełniany od lewej do prawej. Taka struktura umożliwia elegancką reprezentację tablicową, bez marnowania miejsca i bez wskaźników. Własność zupełności gwarantuje, że wysokość kopca zawsze wynosi floor(log₂ n), co zapewnia operacje wstawiania i usuwania o złożoności O(log n).

# Complete binary tree properties:
# 1. All levels filled except possibly the last
# 2. Last level filled from LEFT to right
# 3. For n nodes: height = floor(log2(n))

# NOT complete (last level not left-filled):
#     1
#    / \
#   2   3
#        \
#         4  <- right child without left sibling

# Valid complete binary tree with 4 nodes:
#     1
#    / \
#   2   3
#  /
# 4
print('Complete BT: height = floor(log2(n)) always')

Tablicowa reprezentacja kopca

Struktura zupełnego drzewa binarnego pozwala przechowywać kopiec w zwykłej tablicy bez żadnych wskaźników. Dla węzła o indeksie i (indeksowanie od zera) jego rodzic znajduje się pod indeksem (i-1) // 2, lewe dziecko pod indeksem 2i+1, a prawe dziecko pod indeksem 2i+2. To działanie na liczbach całkowitych zastępuje przechodzenie po wskaźnikach i sprawia, że kopce bardzo dobrze wykorzystują pamięć podręczną procesora.

# Array representation (0-indexed):
# Index:  0  1  2  3  4  5  6
# Array: [1, 3, 2, 7, 4, 5, 6]
# Tree:        1          (index 0)
#             / \         
#            3   2        (indices 1, 2)
#           / \ / \       
#          7  4 5  6      (indices 3,4,5,6)

# Index formulas (0-based):
def parent(i):      return (i - 1) // 2
def left_child(i):  return 2 * i + 1
def right_child(i): return 2 * i + 2

heap = [1, 3, 2, 7, 4, 5, 6]
print('Parent of index 3:', parent(3), '-> value', heap[parent(3)])
print('Left child of 1:', left_child(1), '-> value', heap[left_child(1)])

Przesiewanie w górę: przywracanie własności kopca po wstawieniu

Przesiewanie w górę (nazywane także bubble-up lub heapify-up) stosuje się po wstawieniu nowego elementu na końcu tablicy kopca. Nowy element porównuje się z rodzicem; jeśli własność kopca jest naruszona, elementy zamienia się miejscami i kontynuuje przesuwanie w górę. Operację powtarza się, aż element znajdzie się we właściwym miejscu albo dotrze do korzenia. Ma ona złożoność O(log n), ponieważ wysokość drzewa wynosi O(log n).

def sift_up(heap, i):
    while i > 0:
        p = (i - 1) // 2  # parent index
        if heap[p] > heap[i]:  # min-heap: parent should be smaller
            heap[p], heap[i] = heap[i], heap[p]
            i = p
        else:
            break  # heap property restored

# Demonstrate: insert 0 into an existing min-heap
heap = [1, 3, 2, 7, 4, 5, 6]
heap.append(0)  # add at end
print('Before sift-up:', heap)
sift_up(heap, len(heap) - 1)
print('After sift-up:', heap)  # 0 should bubble to root

Przesiewanie w dół: przywracanie własności kopca po usunięciu

Przesiewanie w dół (heapify-down) stosuje się po usunięciu korzenia. Ostatni element przenosi się do korzenia, a następnie przesuwa w dół, wielokrotnie zamieniając go z mniejszym dzieckiem w przypadku kopca minimalnego, aż własność kopca zostanie przywrócona. Ta operacja również ma złożoność O(log n). Przesiewanie w górę i w dół stanowią podstawowe elementy wszystkich operacji na kopcu.

def sift_down(heap, i, n):
    while True:
        smallest = i
        l = 2 * i + 1  # left child
        r = 2 * i + 2  # right child
        if l < n and heap[l] < heap[smallest]:
            smallest = l
        if r < n and heap[r] < heap[smallest]:
            smallest = r
        if smallest == i:
            break  # already in correct position
        heap[i], heap[smallest] = heap[smallest], heap[i]
        i = smallest

heap = [1, 3, 2, 7, 4, 5, 6]
# Pop min: move last to root, then sift-down
heap[0] = heap[-1]
heap.pop()
print('After move last to root:', heap)
sift_down(heap, 0, len(heap))
print('After sift-down:', heap)  # valid min-heap again

Budowanie kopca z tablicy: algorytm Floyda

Naive wstawianie n elementów pojedynczo ma złożoność O(n log n). Algorytm kopcowania Floyda buduje kopiec w czasie O(n), stosując przesiewanie w dół do każdego węzła niebędącego liściem, zaczynając od ostatniego takiego węzła (indeks n//2 - 1) i cofając się aż do korzenia. Węzły liści są już trywialnymi kopcami, więc wystarczy naprawić węzły wewnętrzne — dlatego łączna praca wynosi O(n), a nie O(n log n).

def build_heap(arr):
    n = len(arr)
    # Start from last non-leaf node: index n//2 - 1
    for i in range(n // 2 - 1, -1, -1):
        sift_down(arr, i, n)
    return arr

arr = [5, 3, 8, 1, 9, 2, 7]
print('Before:', arr)
build_heap(arr)
print('After (min-heap):', arr)  # root should be 1

# Why O(n)? Most nodes are near the bottom (leaves).
# Level k from bottom has ~n/2^k nodes, each needing
# at most k swaps. Sum = n * sum(k/2^k) = O(n).

Sortowanie przez kopcowanie z użyciem kopca tablicowego

Sortowanie przez kopcowanie ma złożoność O(n log n) i wymaga O(1) dodatkowej pamięci. Faza 1: zbudowanie z tablicy kopca maksymalnego w czasie O(n). Faza 2: wielokrotne wydobywanie maksimum przez zamianę korzenia z ostatnim nieposortowanym elementem, a następnie przesiewanie w dół pomniejszonego kopca. Po n operacjach wydobywania tablica jest posortowana rosnąco. Ten algorytm działający w miejscu pokazuje, jak reprezentacja tablicowa umożliwia sortowanie bez przydzielania osobnej struktury danych.

def sift_down_max(arr, i, n):
    while True:
        largest = i
        l, r = 2*i+1, 2*i+2
        if l < n and arr[l] > arr[largest]: largest = l
        if r < n and arr[r] > arr[largest]: largest = r
        if largest == i: break
        arr[i], arr[largest] = arr[largest], arr[i]
        i = largest

def heap_sort(arr):
    n = len(arr)
    # Build max-heap
    for i in range(n // 2 - 1, -1, -1):
        sift_down_max(arr, i, n)
    # Extract elements one by one
    for end in range(n - 1, 0, -1):
        arr[0], arr[end] = arr[end], arr[0]  # move max to end
        sift_down_max(arr, 0, end)

arr = [5, 3, 8, 1, 9, 2, 7]
heap_sort(arr)
print(arr)  # [1, 2, 3, 5, 7, 8, 9]

Kopiec minimalny a kopiec maksymalny

Kopiec minimalny ma najmniejszy element w korzeniu, więc usunięcie korzenia zawsze zwraca minimum. Kopiec maksymalny ma największy element w korzeniu, więc usunięcie korzenia zawsze zwraca maksimum. Oba kopce mają identyczną strukturę i operacje — zmienia się tylko kierunek porównywania. Moduł Pythona heapq implementuje wyłącznie kopiec minimalny, dlatego aby zasymulować kopiec maksymalny, należy negować wartości.

import heapq

# Python heapq is a MIN-HEAP
min_heap = []
heapq.heappush(min_heap, 5)
heapq.heappush(min_heap, 1)
heapq.heappush(min_heap, 3)
print('Min-heap min:', heapq.heappop(min_heap))  # 1

# Simulate MAX-HEAP by negating values
max_heap = []
for val in [5, 1, 3]:
    heapq.heappush(max_heap, -val)  # negate on push
print('Max-heap max:', -heapq.heappop(max_heap))  # 5 (negate on pop)

# For tuples: heapq sorts by first element
print(min_heap, max_heap)

Podsumowanie złożoności operacji na kopcu

Wszystkie operacje na kopcu wynikają z przesiewania w górę i w dół, z których każda ma złożoność O(log n). Wstawianie: dołączenie elementu i przesiewanie w górę = O(log n). Usuwanie: zamiana korzenia z ostatnim elementem i przesiewanie w dół = O(log n). Podejrzenie: dostęp do indeksu 0 = O(1). Budowanie kopca: O(n) dzięki algorytmowi Floyda. Sortowanie przez kopcowanie: O(n log n). Dzięki tym właściwościom kopce są idealną strukturą, gdy trzeba wielokrotnie znajdować minimum lub maksimum w dynamicznej kolekcji.

# Heap complexity summary:
# Operation     | Time       | Space
# --------------|------------|-------
# Push          | O(log n)   | O(1)
# Pop (min/max) | O(log n)   | O(1)
# Peek          | O(1)       | O(1)
# Build from n  | O(n)       | O(1) in-place
# Heap sort     | O(n log n) | O(1)
# nlargest(k,n) | O(n log k) | O(k)

import heapq
data = [5, 3, 8, 1, 9, 2, 7]
print('Top 3 largest:', heapq.nlargest(3, data))  # [9, 8, 7]
print('Top 3 smallest:', heapq.nsmallest(3, data))  # [1, 2, 3]

Praktyczne wzorce użycia kopców podczas rozmów rekrutacyjnych

Kopce rozwiązują całą rodzinę zadań rekrutacyjnych opartych na wspólnym wzorcu: podczas przetwarzania n elementów w strumieniu należy utrzymywać kolejkę priorytetową zawierającą k kandydatów. Najczęściej występujące elementy, k punktów najbliższych początkowi układu oraz planowanie zadań wykorzystują ten wzorzec. Należy go rozpoznać, gdy zadanie mówi: „dany jest strumień n elementów, należy utrzymywać k najlepszych” — zawsze oznacza to użycie kopca o rozmiarze k, dające łączną złożoność O(n log k).

import heapq

# Top-K closest points to origin using a max-heap of size k
def k_closest(points, k):
    # Use max-heap (negate distance) of size k
    heap = []
    for x, y in points:
        dist = -(x*x + y*y)  # negate for max-heap
        heapq.heappush(heap, (dist, x, y))
        if len(heap) > k:
            heapq.heappop(heap)  # remove farthest
    return [[x, y] for _, x, y in heap]

points = [[1,3], [-2,2], [5,8], [0,1]]
print(k_closest(points, 2))  # 2 closest to origin

Kopiec a posortowana tablica — kompromisy

Kopiec należy wybrać, gdy potrzebny jest tylko wielokrotny dostęp do minimum lub maksimum, a kolekcja zmienia się dynamicznie. Posortowaną tablicę należy wybrać, gdy potrzebny jest swobodny dostęp według indeksu lub zapytania zakresowe. Słabością kopca jest wyszukiwanie dowolnych elementów w czasie O(n), a jego zaletą — wstawianie i usuwanie w czasie O(log n) oraz dostęp do minimum lub maksimum w czasie O(1). Posortowana tablica ma złożoność O(n) dla wstawiania, ale umożliwia wyszukiwanie binarne w czasie O(log n).

# Trade-off comparison:
# Structure     | insert  | delete_min | search | range_query
# --------------|---------|------------|--------|------------
# Min-heap      | O(logn) | O(logn)    | O(n)   | O(n)
# Sorted array  | O(n)    | O(n)       | O(logn)| O(logn+k)
# BST (balanced)| O(logn) | O(logn)    | O(logn)| O(logn+k)
# Hash map      | O(1)    | O(1)       | O(1)   | O(n)

# Interview heuristic:
# 'Find minimum repeatedly from dynamic collection' -> HEAP
# 'Binary search or range query' -> sorted array or BST
# 'Fast lookup by key' -> hash map
print('Heap = dynamic collection with priority access')

Szybkie sprawdzenie

Proszę sprawdzić zrozumienie zagadnień Data Structures & Algorithms — Coding Interview Prep omówionych w tej lekcji.

Podsumowanie lekcji

W tej lekcji omówiono: własność kopca i strukturę zupełnego drzewa binarnego, reprezentację tablicową wraz ze wzorami indeksów rodziców i dzieci oraz przesiewanie w górę i w dół jako podstawę wszystkich operacji na kopcu, w tym budowania kopca w czasie O(n) algorytmem Floyda. Następnie zaimplementujemy heapify i poznamy moduł heapq języka Python.

Często zadawane pytania

Czy lekcja „Własność kopca i reprezentacja tablicowa” jest bezpłatna?

Tak — pełny tekst „Własność kopca i reprezentacja tablicowa” jest dostępny za darmo tutaj w sieci. Aby ćwiczyć ją interaktywnie (wbudowany edytor kodu i tutor AI dostępny 24/7) i odblokować resztę kursu Coding Interview Prep, przejdź na CoddyKit PRO. Kurs Coding Interview Prep zawiera 4 lekcji w sumie.

Co nauczysz się w „Własność kopca i reprezentacja tablicowa”?

Zrozumieją Państwo strukturę pełnego drzewa binarnego przechowywaną jako tablica, wyprowadzą wzory indeksów rodzica i dzieci oraz zwizualizują operacje sift-up i sift-down. Ćwiczysz Coding Interview Prep z praktycznym kodem, który uruchamiasz bezpośrednio w przeglądarce, a tutor AI dostępny 24/7 odpowiada na Twoje pytania podczas pracy nad lekcją.

Czy potrzebuję doświadczenia, aby zacząć Coding Interview Prep?

Nie wymagamy żadnego doświadczenia. Coding Interview Prep w CoddyKit jest strukturyzowany dla początkujących i zaawansowanych użytkowników, więc możesz zacząć tutaj lub od początku i uczyć się w swoim tempie. To lekcja 1 z 4.

Ile czasu zajmuje lekcja „Własność kopca i reprezentacja tablicowa”?

Większość lekcji CoddyKit trwa około 5–10 minut. Każda lekcja to mały, interaktywny krok, dzięki czemu robisz systematyczne postępy i zawsze wracasz dokładnie do tego samego miejsca — na webie i w aplikacji.

Czy mogę pisać i uruchamiać kod w tej lekcji Coding Interview Prep?

Tak. Każda lekcja Coding Interview Prep zawiera wbudowany edytor kodu, więc piszesz i uruchamiasz prawdziwy kod bezpośrednio w przeglądarce i od razu otrzymujesz sprzężenie zwrotne od AI — bez konfiguracji na komputerze.

Wszystkie lekcje w tym kursie

  1. Własność kopca i reprezentacja tablicowa
  2. Heapify, push i pop od podstaw
  3. heapq w Pythonie i sztuczki z kopcem maksymalnym
  4. Mediana ze strumienia danych i scalanie k-way
← Powrót do Coding Interview Prep