Heapify, push e pop da zero
Implementi heapify-up per push e heapify-down per pop, poi costruisca in O(n) un heap da un array non ordinato usando l'algoritmo di Floyd
Heapify, push e pop da zero è una lezione DSA Interview Prep gratuita su CoddyKit. Questa è la lezione 2 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 DSA Interview Prep, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso DSA Interview Prep include 4 lezioni in totale.
Creare una classe MinHeap
Implementare un heap da zero dimostra la padronanza dei meccanismi sottostanti e talvolta è richiesto nei colloqui per posizioni senior. Una classe MinHeap racchiude un array ed espone le operazioni push, pop, peek e size. Internamente mantiene la proprietà dell'heap chiamando sift-up dopo push e sift-down dopo pop. Comprendere questa implementazione rende completamente trasparente il funzionamento del modulo heapq di Python.
class MinHeap:
def __init__(self):
self._data = []
def push(self, val):
self._data.append(val)
self._sift_up(len(self._data) - 1)
def pop(self):
if len(self._data) == 1:
return self._data.pop()
min_val = self._data[0]
self._data[0] = self._data.pop() # move last to root
self._sift_down(0)
return min_val
def peek(self):
return self._data[0] if self._data else None
def size(self):
return len(self._data)
def _parent(self, i): return (i - 1) // 2
def _left(self, i): return 2 * i + 1
def _right(self, i): return 2 * i + 2
print('MinHeap class skeleton defined')Implementare sift-up
Sift-up confronta un nodo con il proprio genitore e lo scambia verso l'alto finché la proprietà dell'heap (genitore <= figlio nel min-heap) è violata. Il punto fondamentale è che l'elemento appena inserito si trova alla fine e risale fino alla posizione corretta. Il ciclo while viene eseguito al massimo floor(log n) volte, cioè quanto l'altezza dell'albero. Assegni i = parent a ogni passaggio per continuare a risalire.
class MinHeap:
def __init__(self):
self._data = []
def _parent(self, i): return (i - 1) // 2
def _left(self, i): return 2 * i + 1
def _right(self, i): return 2 * i + 2
def _sift_up(self, i):
while i > 0:
p = self._parent(i)
if self._data[p] > self._data[i]: # parent > child: swap
self._data[p], self._data[i] = self._data[i], self._data[p]
i = p
else:
break # heap property satisfied
def push(self, val):
self._data.append(val)
self._sift_up(len(self._data) - 1)
h = MinHeap()
for v in [5, 3, 8, 1, 4]:
h.push(v)
print(h._data) # valid min-heapImplementare sift-down
Sift-down fa scendere un nodo scambiandolo ripetutamente con il figlio più piccolo (nel min-heap), finché nessuno dei due figli è più piccolo oppure il nodo raggiunge una foglia. Confronti sempre entrambi i figli e scambi il nodo con quello più piccolo per mantenere la proprietà dell'heap. Si ricordi di verificare che gli indici dei figli siano nei limiti prima di confrontare i valori.
def _sift_down(data, i):
n = len(data)
while True:
smallest = i
l = 2 * i + 1
r = 2 * i + 2
if l < n and data[l] < data[smallest]:
smallest = l
if r < n and data[r] < data[smallest]:
smallest = r
if smallest == i:
break # already the smallest among i, l, r
data[i], data[smallest] = data[smallest], data[i]
i = smallest
# Test: put a large value at root and sift down
heap = [10, 1, 2, 3, 4, 5, 6]
print('Before sift-down:', heap)
_sift_down(heap, 0)
print('After sift-down:', heap) # 1 should reach top, 10 sinkCompletare MinHeap con pop
L'operazione pop rimuove e restituisce la radice (il minimo nel min-heap). Per mantenere la forma dell'albero binario completo, sposti l'ultimo elemento nella posizione della radice, quindi esegua sift-down. In questo modo evita di creare spazi vuoti nell'array e mantiene valida la rappresentazione. Caso limite: se rimane un solo elemento, lo estragga e lo restituisca direttamente senza eseguire sift-down.
class MinHeap:
def __init__(self):
self._data = []
def push(self, val):
self._data.append(val)
i = len(self._data) - 1
while i > 0:
p = (i - 1) // 2
if self._data[p] > self._data[i]:
self._data[p], self._data[i] = self._data[i], self._data[p]
i = p
else: break
def pop(self):
if not self._data: return None
if len(self._data) == 1: return self._data.pop()
result = self._data[0]
self._data[0] = self._data.pop() # last -> root
i, n = 0, len(self._data)
while True:
s, l, r = i, 2*i+1, 2*i+2
if l < n and self._data[l] < self._data[s]: s = l
if r < n and self._data[r] < self._data[s]: s = r
if s == i: break
self._data[i], self._data[s] = self._data[s], self._data[i]
i = s
return result
h = MinHeap()
for v in [5, 3, 8, 1, 4, 2]: h.push(v)
print([h.pop() for _ in range(6)]) # [1,2,3,4,5,8] sortedAlgoritmo heapify di Floyd
L'algoritmo di Floyd costruisce un min-heap da un array non ordinato in O(n) chiamando sift-down su ogni nodo non foglia, iniziando dall'ultimo nodo interno (n//2 - 1) e procedendo verso la radice. Le foglie sono già heap validi di un solo elemento. Il limite temporale O(n) deriva dal fatto che la maggior parte dei nodi si trova vicino alla base dell'albero e deve scendere solo di una distanza ridotta.
def heapify(arr):
n = len(arr)
# Start from last non-leaf: index n//2 - 1
# Work backward to root (index 0)
for i in range(n // 2 - 1, -1, -1):
# Sift down node at index i
j = i
while True:
s = j
l, r = 2*j+1, 2*j+2
if l < n and arr[l] < arr[s]: s = l
if r < n and arr[r] < arr[s]: s = r
if s == j: break
arr[j], arr[s] = arr[s], arr[j]
j = s
return arr
arr = [9, 7, 5, 3, 1, 8, 2, 4, 6]
print('Before:', arr)
heapify(arr)
print('After (min-heap):', arr) # arr[0] should be 1Perché l'algoritmo di Floyd è O(n)
La dimostrazione di O(n): l'albero contiene n/2^(k+1) nodi ad altezza k. Ogni nodo ad altezza k esegue al massimo k scambi durante sift-down. Il lavoro totale è uguale alla somma, su tutte le altezze k, di n/2^(k+1) * k. Questa serie geometrica converge a O(n). Al contrario, l'inserimento ingenuo uno alla volta richiede O(log n) per ogni push, quindi n push costano O(n log n). L'algoritmo di Floyd è strettamente migliore per la costruzione in blocco.
import time
import random
# Compare: O(n) heapify vs O(n log n) one-by-one
n = 100000
data = list(range(n, 0, -1)) # reverse sorted = worst case for push
# Method 1: Floyd's O(n)
data1 = data[:]
start = time.time()
for i in range(n // 2 - 1, -1, -1):
j = i
while True:
s = j; l, r = 2*j+1, 2*j+2
if l < n and data1[l] < data1[s]: s = l
if r < n and data1[r] < data1[s]: s = r
if s == j: break
data1[j], data1[s] = data1[s], data1[j]; j = s
print(f'Floyd heapify: {time.time()-start:.4f}s')
# Method 2: One-by-one insertion
import heapq
start = time.time()
heap = []
for x in data: heapq.heappush(heap, x)
print(f'Push one-by-one: {time.time()-start:.4f}s')Inserire elementi in una raccolta esistente tramite heap
heapq.heappushpop e heapq.heapreplace di Python sono operazioni combinate efficienti. heappushpop(heap, item) inserisce il nuovo elemento ed estrae immediatamente il più piccolo, risultando più efficiente di due chiamate separate. heapreplace(heap, item) estrae il più piccolo e inserisce il nuovo elemento in un unico passaggio (per essere corretto, il nuovo elemento deve essere >= il minimo precedente). Queste operazioni sono utili negli algoritmi in streaming per i primi k elementi.
import heapq
heap = [1, 3, 5, 7, 9]
heapq.heapify(heap)
# heappushpop: push 2, then pop minimum
# More efficient than push + pop separately
result = heapq.heappushpop(heap, 2)
print('heappushpop(2):', result, '| heap:', heap)
# heapreplace: pop minimum, then push new item
# New item does NOT need to be larger (different from heappushpop)
result2 = heapq.heapreplace(heap, 4)
print('heapreplace(4):', result2, '| heap:', heap)
# Use case: maintaining a fixed-size top-k heap
# heappushpop is the standard patternImplementare un MaxHeap da zero
Un MaxHeap inverte il confronto: il genitore deve essere maggiore o uguale a tutti i discendenti. È sufficiente invertire il confronto in sift-up e sift-down. In alternativa, può racchiudere i valori in una classe che ne calcola la negazione oppure negare gli interi, come si fa con heapq di Python. Implementare un heap da zero dimostra che min-heap e max-heap sono strutture identiche, in cui cambia soltanto l'operatore di confronto.
class MaxHeap:
def __init__(self):
self._data = []
def push(self, val):
self._data.append(val)
i = len(self._data) - 1
while i > 0:
p = (i - 1) // 2
if self._data[p] < self._data[i]: # FLIP: parent < child = violation
self._data[p], self._data[i] = self._data[i], self._data[p]
i = p
else: break
def pop(self):
if not self._data: return None
if len(self._data) == 1: return self._data.pop()
result = self._data[0]
self._data[0] = self._data.pop()
i, n = 0, len(self._data)
while True:
g = i; l, r = 2*i+1, 2*i+2
if l < n and self._data[l] > self._data[g]: g = l # FLIP
if r < n and self._data[r] > self._data[g]: g = r # FLIP
if g == i: break
self._data[i], self._data[g] = self._data[g], self._data[i]; i = g
return result
h = MaxHeap()
for v in [5, 3, 8, 1, 4, 2]: h.push(v)
print([h.pop() for _ in range(6)]) # [8,5,4,3,2,1]Eliminare un elemento arbitrario da un heap
Eliminare un elemento arbitrario (non la radice) da un heap richiede O(log n), ma è necessario conoscere l'indice dell'elemento. Sostituisca l'elemento con l'ultimo, rimuova l'ultimo, quindi esegua sift-up o sift-down sull'elemento sostitutivo (solo una delle due direzioni violerà la proprietà dell'heap). Questa tecnica viene usata nell'algoritmo di Dijkstra con l'eliminazione differita e nelle code con priorità che supportano le operazioni decrease-key.
def delete_at_index(heap, i):
n = len(heap)
heap[i] = heap[n - 1]
heap.pop()
if i >= len(heap):
return # deleted the last element
# Try sift-up first
p = (i - 1) // 2
if i > 0 and heap[i] < heap[p]:
while i > 0:
p = (i - 1) // 2
if heap[p] > heap[i]:
heap[p], heap[i] = heap[i], heap[p]; i = p
else: break
else: # sift down
j = i; n2 = len(heap)
while True:
s = j; l, r = 2*j+1, 2*j+2
if l < n2 and heap[l] < heap[s]: s = l
if r < n2 and heap[r] < heap[s]: s = r
if s == j: break
heap[j], heap[s] = heap[s], heap[j]; j = s
heap = [1, 3, 2, 7, 4, 5, 6]
print('Before:', heap)
delete_at_index(heap, 2) # delete element at index 2 (value=2)
print('After:', heap) # 2 removed, heap still validHeap per gli elementi più frequenti tra i Top-K
Top-K Frequent Elements (LeetCode #347) usa un min-heap di dimensione k. Mantenga un min-heap in cui ogni voce è (frequency, element). Elabori ogni elemento distinto: se l'heap contiene meno di k elementi, esegua push; altrimenti, se la frequenza del nuovo elemento supera il minimo dell'heap, esegua pop e push. L'heap finale contiene i k elementi più frequenti in tempo O(n log k).
import heapq
from collections import Counter
def top_k_frequent(nums, k):
count = Counter(nums)
# Min-heap of (frequency, num)
heap = []
for num, freq in count.items():
heapq.heappush(heap, (freq, num))
if len(heap) > k:
heapq.heappop(heap) # remove least frequent
return [num for freq, num in heap]
print(top_k_frequent([1,1,1,2,2,3], 2)) # [1, 2]
print(top_k_frequent([4,4,4,3,3,2,1], 2)) # [4, 3]Applicazioni degli heap nella schedulazione
Oltre alla programmazione competitiva, gli heap sono alla base dei sistemi di schedulazione reali. Gli scheduler delle attività dei sistemi operativi usano una coda con priorità (heap) per eseguire sempre il processo pronto con la priorità più alta. Le simulazioni basate sugli eventi elaborano gli eventi in ordine temporale usando un min-heap ordinato in base all'istante dell'evento. Gli scheduler dei pacchetti di rete assegnano la priorità al traffico in base alla classe di qualità del servizio. Comprendere gli heap fornisce un modello mentale per tutti questi sistemi ed è utile naturalmente nei colloqui di system design dedicati a code e schedulazione.
import heapq
# Simple event-driven simulation using a heap
events = [] # (time, event_description)
def schedule(time, event):
heapq.heappush(events, (time, event))
def process_next():
time, event = heapq.heappop(events)
print(f't={time}: {event}')
return time, event
# Schedule events out of order:
schedule(10, 'Send email')
schedule(3, 'Open app')
schedule(7, 'Process request')
schedule(1, 'Start server')
# Process in time order:
while events:
process_next()
# Output: t=1, t=3, t=7, t=10 -- always in time orderVerifica rapida
Verifichi la Sua comprensione dei concetti di Data Structures & Algorithms — Coding Interview Prep trattati in questa lezione.
Riepilogo della lezione
In questa lezione ha imparato a implementare MinHeap e MaxHeap da zero con sift-up e sift-down, l'algoritmo di heapify O(n) di Floyd e il motivo per cui è più efficiente dell'inserimento uno alla volta in O(n log n), oltre ad alcune applicazioni pratiche, tra cui gli elementi top-k più frequenti e la cancellazione tramite indice. Nella prossima lezione esploreremo il modulo heapq di Python e i metodi per simulare un max-heap.
Domande Frequenti
La lezione «Heapify, push e pop da zero» è gratuita?
Sì — il testo completo di «Heapify, push e pop da zero» è 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 DSA Interview Prep, passa a CoddyKit PRO. Il corso DSA Interview Prep include 4 lezioni in totale.
Cosa imparerò in «Heapify, push e pop da zero»?
Implementi heapify-up per push e heapify-down per pop, poi costruisca in O(n) un heap da un array non ordinato usando l'algoritmo di Floyd Eserciti DSA 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 DSA Interview Prep?
Non è richiesta alcuna esperienza precedente. DSA 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 2 di 4.
Quanto tempo richiede la lezione «Heapify, push e pop da zero»?
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 DSA Interview Prep?
Sì. Ogni lezione DSA 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
- Proprietà degli heap e rappresentazione tramite array
- Heapify, push e pop da zero
- heapq di Python e trucchi per il max-heap
- Mediana da un flusso di dati e merge k-way