PricingLoginStart free
DSA Interview Prep · Pelajaran

Heapify, Push dan Pop dari Awal

Laksanakan heapify-up untuk push dan heapify-down untuk pop, kemudian bina heap daripada tatasusunan tidak tersusun dalam O(n) menggunakan algoritma Floyd.

Pelajaran 2 daripada 413 langkah

Heapify, Push dan Pop dari Awal ialah pelajaran DSA Interview Prep percuma di CoddyKit. Ini ialah pelajaran 2 daripada 4. Sebanyak 3 pelajaran dalam laluan pembelajaran ini boleh dibaca sepenuhnya secara percuma — selepas itu, CoddyKit PRO membuka akses kepada semua pelajaran, serta latihan praktikal dengan penyunting kod terbina dalam dan tutor kecerdasan buatan yang tersedia 24/7. Pelajaran ini merupakan sebahagian daripada laluan pembelajaran DSA Interview Prep, dan kemajuan anda disegerakkan merentas web serta aplikasi CoddyKit. Kursus DSA Interview Prep merangkumi sejumlah 4 pelajaran.

Melaksanakan Kelas MinHeap

Melaksanakan timbunan dari awal menunjukkan penguasaan terhadap mekanik asasnya dan kadangkala ditanya dalam temu duga peringkat kanan. Kelas MinHeap membalut tatasusunan serta mendedahkan operasi push, pop, peek dan size. Secara dalaman, kelas ini mengekalkan sifat timbunan dengan memanggil pengalihan ke atas selepas push dan pengalihan ke bawah selepas pop. Memahami pelaksanaan ini menjadikan modul heapq Python mudah difahami sepenuhnya.

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

Melaksanakan Pengalihan ke Atas

Pengalihan ke atas membandingkan nod dengan parentnya dan menukarkannya ke atas selagi sifat timbunan (parent <= anak bagi timbunan minimum) dilanggar. Perkara pentingnya ialah elemen yang baru disisipkan berada di hujung dan bergerak ke atas sehingga mencapai kedudukan yang betul. Gelung while berjalan paling banyak floor(log n) kali — iaitu ketinggian pokok. Tetapkan i = parent pada setiap langkah untuk terus bergerak ke atas.

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-heap

Melaksanakan Pengalihan ke Bawah

Pengalihan ke bawah menolak nod ke bawah dengan menukarkannya berulang kali dengan anak terkecilnya (untuk timbunan minimum), sehingga tiada anak yang lebih kecil atau nod tersebut mencapai daun. Sentiasa bandingkan dengan kedua-dua anak dan tukarkan dengan anak yang lebih kecil untuk mengekalkan sifat timbunan. Ingat untuk memastikan indeks anak berada dalam sempadan sebelum membandingkan nilai.

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 sink

Melengkapkan MinHeap dengan pop

Operasi pop mengeluarkan dan mengembalikan akar, iaitu nilai minimum bagi timbunan minimum. Untuk mengekalkan bentuk pokok binari lengkap, pindahkan elemen terakhir ke kedudukan akar, kemudian lakukan pengalihan ke bawah. Cara ini mengelakkan pembentukan jurang dalam tatasusunan dan memastikan perwakilan kekal sah. Kes tepi: jika hanya satu elemen yang tinggal, lakukan pop dan kembalikannya terus tanpa pengalihan ke bawah.

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

Algoritma Heapify Floyd

Algoritma Floyd membina timbunan minimum daripada tatasusunan tidak tersusun dalam O(n) dengan memanggil pengalihan ke bawah pada setiap nod bukan daun, bermula daripada nod dalaman terakhir (n//2 - 1) dan bergerak menuju akar. Daun sudah merupakan timbunan satu elemen yang sah secara asas. Had time O(n) terhasil kerana kebanyakan nod berada berhampiran bahagian bawah pokok dan hanya perlu dialihkan ke bawah sejauh jarak yang kecil.

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 1

Mengapa Algoritma Floyd ialah O(n)

Bukti O(n): pokok mempunyai n/2^(k+1) nod pada ketinggian k. Setiap nod pada ketinggian k melakukan paling banyak k pertukaran semasa pengalihan ke bawah. Jumlah kerja = jumlah bagi semua ketinggian k: n/2^(k+1) * k. Siri geometri ini menghampiri O(n). Bandingkan dengan penyisipan satu demi satu secara naif: setiap push mengambil O(log n), jadi n operasi push menelan kos O(n log n). Algoritma Floyd sememangnya lebih baik untuk pembinaan secara kelompok.

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

Push Timbunan ke dalam Koleksi Sedia Ada

heapq.heappushpop dan heapq.heapreplace Python ialah operasi gabungan yang cekap. heappushpop(heap, item) melakukan push terhadap item baharu dan serta-merta melakukan pop terhadap item terkecil — lebih cekap daripada dua panggilan berasingan. heapreplace(heap, item) melakukan pop terhadap item terkecil dan melakukan push terhadap item baharu dalam satu laluan (item baharu mestilah >= minimum lama untuk memastikan ketepatan). Operasi ini berguna dalam algoritma penstriman K teratas.

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 pattern

Melaksanakan MaxHeap dari Awal

MaxHeap membalikkan perbandingan: parent mestilah lebih besar daripada atau sama dengan semua keturunannya. Balikkan sahaja perbandingan dalam pengalihan ke atas dan pengalihan ke bawah. Sebagai alternatif, balut nilai dalam kelas penafian atau nafikan integer seperti yang dilakukan dengan heapq Python. Pelaksanaan dari awal menunjukkan bahawa timbunan minimum dan maksimum ialah struktur yang sama, dengan hanya operator perbandingan yang berubah.

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]

Memadam Elemen Sewenang-wenangnya daripada Timbunan

Memadam elemen sewenang-wenangnya (bukan akar) daripada timbunan mengambil O(log n), tetapi memerlukan pengetahuan tentang indeks elemen tersebut. Gantikan elemen itu dengan elemen terakhir, keluarkan elemen terakhir, kemudian lakukan pengalihan ke atas atau pengalihan ke bawah terhadap pengganti tersebut (hanya satu arah akan melanggar sifat timbunan). Teknik ini digunakan dalam algoritma Dijkstra dengan pemadaman tertangguh dan dalam baris gilir keutamaan yang menyokong operasi pengurangan kekunci.

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 valid

Timbunan bagi K Elemen Paling Kerap

K Elemen Paling Kerap (LeetCode #347) menggunakan timbunan minimum bersaiz k. Kekalkan timbunan minimum yang setiap entrinya ialah (frequency, element). Proses setiap elemen unik: jika timbunan mempunyai kurang daripada k elemen, lakukan push; jika tidak, jika kekerapan elemen baharu melebihi minimum timbunan, lakukan pop dan push. Timbunan akhir mengandungi k elemen paling kerap dalam O(n log k) time.

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]

Aplikasi Timbunan dalam Penjadualan

Selain pengaturcaraan kompetitif, timbunan menggerakkan sistem penjadualan dunia sebenar. Penjadual tugas sistem pengendalian menggunakan baris gilir keutamaan (timbunan) untuk sentiasa menjalankan proses sedia dengan keutamaan tertinggi. Simulasi dipacu peristiwa memproses peristiwa mengikut susunan masa menggunakan timbunan minimum yang diindeks berdasarkan masa peristiwa. Penjadual paket rangkaian mengutamakan trafik mengikut kelas kualiti perkhidmatan. Memahami timbunan memberikan anda model mental untuk semua sistem ini dan muncul secara semula jadi dalam temu duga reka bentuk sistem tentang baris gilir dan penjadualan.

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 order

Semakan Pantas

Uji pemahaman anda tentang konsep Struktur Data & Algoritma — Persediaan Temu Duga Pengekodan daripada pelajaran ini.

Jawab dalam pelajaran interaktif

Ringkasan Pelajaran

Dalam pelajaran ini anda mempelajari: MinHeap dan MaxHeap dari awal dengan pelarasan ke atas dan pelarasan ke bawah, algoritma heapify O(n) Floyd dan sebab algoritma ini mengatasi penyisipan satu demi satu O(n log n), serta aplikasi praktikal termasuk elemen k teratas yang paling kerap muncul dan pemadaman pada indeks. Seterusnya kita meneroka modul heapq Python dan helah timbunan maksimum.

Percuma untuk bermula

Pelajari Python dengan tutor kecerdasan buatan — percuma

Tulis dan jalankan kod sebenar dalam pelayar anda, dapatkan bantuan segera daripada tutor kecerdasan buatan yang tersedia 24/7, dan sambung semula dari tempat anda berhenti di web atau dalam aplikasi.

Kursus
30
Pelajaran
120
Mula belajar secara percumaLihat kursus penuh

Soalan Lazim

Adakah pelajaran “Heapify, Push dan Pop dari Awal” percuma?

Ya — sebanyak 3 pelajaran dalam laluan pembelajaran DSA Interview Prep, termasuk “Heapify, Push dan Pop dari Awal”, boleh dibaca sepenuhnya secara percuma di web ini. Selepas itu, CoddyKit PRO membuka akses kepada semua pelajaran, serta latihan interaktif dengan penyunting kod terbina dalam dan tutor kecerdasan buatan yang tersedia 24/7. Kursus DSA Interview Prep merangkumi sejumlah 4 pelajaran.

Apakah yang akan saya pelajari dalam “Heapify, Push dan Pop dari Awal”?

Laksanakan heapify-up untuk push dan heapify-down untuk pop, kemudian bina heap daripada tatasusunan tidak tersusun dalam O(n) menggunakan algoritma Floyd. Anda berlatih DSA Interview Prep menggunakan kod praktikal yang dijalankan terus dalam pelayar, manakala tutor kecerdasan buatan 24/7 menjawab soalan anda semasa anda mengikuti pelajaran.

Adakah saya memerlukan pengalaman untuk memulakan DSA Interview Prep?

Tiada pengalaman terdahulu diperlukan. Pembelajaran DSA Interview Prep di CoddyKit disusun untuk pelajar daripada peringkat pemula hingga lanjutan, jadi anda boleh bermula di sini atau dari awal dan belajar mengikut kadar anda sendiri. Ini ialah pelajaran 2 daripada 4.

Berapa lamakah pelajaran “Heapify, Push dan Pop dari Awal” diambil?

Kebanyakan pelajaran CoddyKit mengambil masa kira-kira 5–10 minit. Setiap pelajaran ringkas dan interaktif, jadi anda boleh membuat kemajuan secara berterusan dan menyambung tepat dari tempat anda berhenti di web atau aplikasi.

Bolehkah saya menulis dan menjalankan kod dalam pelajaran DSA Interview Prep ini?

Ya. Setiap pelajaran DSA Interview Prep menyertakan penyunting kod terbina dalam, jadi anda boleh menulis dan menjalankan kod sebenar terus dalam pelayar serta menerima maklum balas kecerdasan buatan serta-merta — tanpa memerlukan persediaan setempat.

Semua pelajaran dalam kursus ini

  1. Sifat Heap dan Perwakilan Tatasusunan
  2. Heapify, Push dan Pop dari Awal
  3. heapq Python dan Helah Max-Heap
  4. Median daripada Strim Data dan Gabungan K-Hala
← Kembali ke DSA Interview Prep