0Pricing
Coding Interview Prep · Lezione

Proprietà degli heap e rappresentazione tramite array

Comprenda la struttura dell'albero binario completo memorizzata come array, ricavi le formule degli indici di genitori e figli e visualizzi le operazioni sift-up e sift-down

Proprietà degli heap e rappresentazione tramite array è una lezione Coding Interview Prep gratuita su CoddyKit. Questa è la lezione 1 di 4. Puoi leggere la lezione completa qui gratuitamente — poi esercitati direttamente nel browser con un editor di codice integrato e un tutor IA disponibile 24/7. Fa parte del percorso di apprendimento Coding Interview Prep, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso Coding Interview Prep include 4 lezioni in totale.

Che cos'è un heap?

Un heap è un albero binario completo specializzato che soddisfa la proprietà dell'heap: in un min-heap, ogni genitore è minore o uguale ai propri figli; in un max-heap, ogni genitore è maggiore o uguale ai propri figli. Questa proprietà garantisce che l'elemento minimo (o massimo) si trovi sempre nella radice, consentendo di accedere in O(1) all'elemento estremo. Gli heap sono la struttura dati alla base delle code con priorità.

# 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')

Struttura dell'albero binario completo

Un heap è memorizzato come un albero binario completo: tutti i livelli sono completamente riempiti, tranne eventualmente l'ultimo, che viene riempito da sinistra verso destra. Questa struttura consente l'elegante rappresentazione tramite array, senza spazio sprecato e senza puntatori. La proprietà di completezza garantisce che l'altezza dell'heap sia sempre floor(log₂ n), assicurando operazioni di inserimento ed estrazione in 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')

Rappresentazione di un heap tramite array

La struttura dell'albero binario completo consente di memorizzare un heap in un semplice array senza puntatori. Per un nodo all'indice i (con indicizzazione a partire da 0), il genitore si trova a (i-1) // 2, il figlio sinistro a 2i+1 e il figlio destro a 2i+2. Questa aritmetica intera sostituisce l'attraversamento tramite puntatori e rende gli heap estremamente efficienti per la cache.

# 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)])

Sift-up: ripristinare l'heap dopo un inserimento

Il sift-up (chiamato anche bubble-up o heapify-up) viene usato dopo aver inserito un nuovo elemento alla fine dell'array dell'heap. Confronti il nuovo elemento con il genitore; se la proprietà dell'heap è violata, li scambi e continui verso l'alto. Ripeta l'operazione finché l'elemento non si trova nella posizione corretta o raggiunge la radice. L'operazione richiede O(log n), perché l'altezza dell'albero è 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

Sift-down: ripristinare l'heap dopo un'estrazione

Il sift-down (heapify-down) viene usato dopo aver rimosso la radice. Sposti l'ultimo elemento nella radice, quindi lo faccia scendere scambiandolo ripetutamente con il figlio più piccolo (nel min-heap) finché la proprietà dell'heap non viene ripristinata. Anche questa operazione richiede O(log n). Sift-up e sift-down sono i mattoni fondamentali di tutte le operazioni sugli heap.

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

Creare un heap da un array: algoritmo di Floyd

Inserire ingenuamente n elementi uno alla volta richiede O(n log n). L'algoritmo heapify di Floyd costruisce un heap in O(n) applicando sift-down a ogni nodo non foglia, iniziando dall'ultima foglia (indice n//2 - 1) e procedendo a ritroso fino alla radice. I nodi foglia sono già heap validi per definizione, quindi è sufficiente correggere i nodi interni: per questo il lavoro totale è O(n) anziché 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).

Heap sort con l'heap rappresentato tramite array

Heap sort richiede O(n log n) e O(1) spazio aggiuntivo. Fase 1: costruire un max-heap dall'array in O(n). Fase 2: estrarre ripetutamente il massimo scambiando la radice con l'ultimo elemento non ordinato, quindi eseguire sift-down sull'heap ridotto. Dopo n estrazioni, l'array è ordinato in ordine crescente. Questo algoritmo in-place dimostra come la rappresentazione tramite array consenta di ordinare senza allocare una struttura dati separata.

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]

Min-heap e max-heap a confronto

Un min-heap ha l'elemento più piccolo nella radice; l'estrazione restituisce sempre il minimo. Un max-heap ha l'elemento più grande nella radice; l'estrazione restituisce sempre il massimo. La struttura e le operazioni sono identiche: cambia soltanto la direzione del confronto. Il modulo heapq di Python implementa esclusivamente un min-heap, quindi è necessario negare i valori per simulare un max-heap.

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)

Riepilogo della complessità delle operazioni sugli heap

Tutte le operazioni sugli heap derivano da sift-up e sift-down, entrambe in O(log n). Push: append + sift-up = O(log n). Pop: scambio della radice con l'ultimo elemento + sift-down = O(log n). Peek: accesso all'indice 0 = O(1). Creazione dell'heap: O(n) tramite l'algoritmo di Floyd. Heap sort: O(n log n). Queste complessità rendono gli heap la struttura ideale quando è necessario trovare ripetutamente il minimo o il massimo di una raccolta dinamica.

# 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]

Modelli pratici con gli heap nei colloqui

Gli heap risolvono una famiglia di problemi da colloquio basati su un modello comune: mantenere una coda con priorità di k candidati durante l'elaborazione in streaming di n elementi. Gli elementi più frequenti tra i primi k, i k punti più vicini all'origine e la pianificazione delle attività usano tutti questo modello. Lo riconosca quando legge: «dato un flusso di n elementi, mantenga i k migliori»: in questo caso serve sempre un heap di dimensione k, con un tempo totale 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

Heap e array ordinato: compromessi

Scelga un heap quando le servono soltanto accessi ripetuti al minimo o al massimo e la raccolta cambia dinamicamente. Scelga un array ordinato quando le servono l'accesso casuale tramite indice o le query sugli intervalli. Il punto debole dell'heap è la ricerca di elementi arbitrari, che richiede O(n); il suo punto di forza è l'inserimento e l'eliminazione in O(log n) e l'accesso al minimo o al massimo in O(1). Un array ordinato richiede O(n) per l'inserimento, ma consente la ricerca binaria in 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')

Verifica rapida

Verifichi la sua comprensione dei concetti di Data Structures & Algorithms — Coding Interview Prep presentati in questa lezione.

Riepilogo della lezione

In questa lezione ha imparato la proprietà dell'heap e la struttura dell'albero binario completo, la rappresentazione tramite array con le formule degli indici di genitori e figli e sift-up e sift-down come mattoni fondamentali di tutte le operazioni sugli heap, inclusa la creazione in O(n) di Floyd. Ora implementeremo heapify ed esploreremo il modulo heapq di Python.

Domande Frequenti

La lezione «Proprietà degli heap e rappresentazione tramite array» è gratuita?

Sì — il testo completo di «Proprietà degli heap e rappresentazione tramite array» è gratuito qui sul web. Per esercitarvi in modo interattivo (un editor di codice integrato e un tutor IA 24/7) e sbloccare il resto del corso Coding Interview Prep, passa a CoddyKit PRO. Il corso Coding Interview Prep include 4 lezioni in totale.

Cosa imparerò in «Proprietà degli heap e rappresentazione tramite array»?

Comprenda la struttura dell'albero binario completo memorizzata come array, ricavi le formule degli indici di genitori e figli e visualizzi le operazioni sift-up e sift-down Eserciti Coding Interview Prep con codice pratico che esegui direttamente nel browser, e un tutor IA 24/7 risponde alle tue domande mentre lavori sulla lezione.

Ho bisogno di esperienza per iniziare Coding Interview Prep?

Non è richiesta alcuna esperienza precedente. Coding Interview Prep su CoddyKit è strutturato per principianti e studenti avanzati, quindi puoi iniziare da qui o dall'inizio e procedere al tuo ritmo. Questa è la lezione 1 di 4.

Quanto tempo richiede la lezione «Proprietà degli heap e rappresentazione tramite array»?

La maggior parte delle lezioni CoddyKit richiede circa 5–10 minuti. Ogni lezione è breve e interattiva, quindi fai progressi costanti e riprendi esattamente da dove hai lasciato su web e app.

Posso scrivere ed eseguire codice in questa lezione Coding Interview Prep?

Sì. Ogni lezione Coding Interview Prep include un editor di codice integrato, quindi scrivi ed esegui codice reale direttamente nel tuo browser e ricevi feedback istantaneo dall'IA — nessuna configurazione locale necessaria.

Tutte le lezioni di questo corso

  1. Proprietà degli heap e rappresentazione tramite array
  2. Heapify, push e pop da zero
  3. heapq di Python e trucchi per il max-heap
  4. Mediana da un flusso di dati e merge k-way
← Torna a Coding Interview Prep