DSA Interview Prep · Ders

Yığın Oluşturma, Ekleme ve Çıkarma İşlemlerini Sıfırdan Uygulama

Ekleme için yukarı doğru, çıkarma için aşağı doğru yığın düzenleme işlemlerini uygulayın; ardından Floyd algoritmasıyla sıralanmamış bir diziden O(n) sürede yığın oluşturun.

2. ders / 413 adım

Yığın Oluşturma, Ekleme ve Çıkarma İşlemlerini Sıfırdan Uygulama, CoddyKit'te ücretsiz bir DSA Interview Prep dersidir. Bu, 4 dersinin 2. dersidir. Aşağıdan dersin tamamını ücretsiz okuyabilir, sonra tarayıcıda yerleşik kod editörü ve 7/24 yapay zeka koçu ile uygulamalı olarak pratik yapabilirsin. Bu, DSA Interview Prep öğrenme yolunun bir parçasıdır ve ilerlemeniz web ve CoddyKit uygulaması arasında senkronize olur. DSA Interview Prep kursu toplamda 4 dersten oluşur.

MinHeap Sınıfı Oluşturma

Sıfırdan bir yığın uygulamak, temel mekanizmalara hâkim olduğunuzu gösterir ve zaman zaman kıdemli geliştirici mülakatlarında sorulur. Bir MinHeap sınıfı, bir diziyi kapsüller ve push, pop, peek ve size işlemlerini sunar. Dahili olarak, push işleminden sonra yukarı süzme ve pop işleminden sonra aşağı süzme çağırarak yığın özelliğini korur. Bu uygulamayı anlamak, Python'ın heapq modülünü tamamen anlaşılır hâle getirir.

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

Yukarı Süzmeyi Uygulama

Yukarı süzme, bir düğümü parent ile karşılaştırır ve yığın özelliği (minimum yığınında parent <= çocuk) ihlal edildiği sürece yukarı doğru yerini değiştirir. Buradaki temel nokta, yeni eklenen öğenin sonda bulunması ve doğru konumuna doğru yukarı çıkmasıdır. Döngü en fazla floor(log n) kez çalışır; bu, ağacın yüksekliğidir. Yukarı doğru ilerlemeyi sürdürmek için her adımda i = parent atamasını yapın.

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

Aşağı Süzmeyi Uygulama

Aşağı süzme, bir düğümü en küçük çocuğuyla (minimum yığını için) tekrar tekrar yer değiştirerek aşağı iter; bu işlem, çocukların hiçbiri daha küçük olmayana veya düğüm bir yaprağa ulaşana kadar sürer. Her zaman iki çocuğu karşılaştırın ve yığın özelliğini korumak için daha küçük olanla yer değiştirin. Değerleri karşılaştırmadan önce çocuk indekslerinin sınırlar içinde olduğunu kontrol etmeyi unutmayın.

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

Pop ile MinHeap'i Tamamlama

pop işlemi, kökü (minimum yığını için minimum değeri) kaldırır ve döndürür. Tam ikili ağacın şeklini korumak için son öğeyi kök konumuna taşıyın ve ardından aşağı süzme uygulayın. Böylece dizide boşluklar oluşmaz ve gösterim geçerli kalır. Uç durum: yalnızca bir öğe kaldıysa, aşağı süzme uygulamadan doğrudan pop edip bu öğeyi döndürün.

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

Floyd'un heapify Algoritması

Floyd'un algoritması, son iç düğümden (n//2 - 1) başlayıp köke doğru ilerleyerek yaprak olmayan her düğümde aşağı süzme çağırmak suretiyle sıralanmamış bir diziden O(n) maliyetle bir minimum yığını oluşturur. Yapraklar zaten geçerli tek öğeli yığınlardır. O(n) time sınırının nedeni, düğümlerin çoğunun ağacın alt kısmına yakın olması ve yalnızca kısa bir mesafe boyunca aşağı süzülmesinin gerekmesidir.

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

Floyd Algoritması Neden O(n)

O(n) kanıtı şöyledir: ağaçta k yüksekliğinde n/2^(k+1) düğüm bulunur. k yüksekliğindeki her düğüm, aşağı süzme sırasında en fazla k kez yer değiştirebilir. Toplam iş = tüm k yükseklikleri için toplam: n/2^(k+1) * k. Bu geometrik seri O(n) değerine yakınsar. Basit tek tek eklemeyle karşılaştırıldığında her push O(log n) maliyetindedir; dolayısıyla n push işlemi O(n log n) maliyetine çıkar. Toplu oluşturma için Floyd algoritması kesinlikle daha iyidir.

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

Mevcut Koleksiyona Push ile Ekleme

Python'ın heapq.heappushpop ve heapq.heapreplace işlevleri verimli birleşik işlemlerdir. heappushpop(heap, item), yeni öğeyi ekler ve hemen en küçüğü çıkarır; bu, iki ayrı çağrıdan daha verimlidir. heapreplace(heap, item), en küçüğü çıkarıp yeni öğeyi tek geçişte ekler (doğru çalışması için yeni öğe eski minimumdan >= olmalıdır). Bunlar, en iyi k öğenin izlendiği veri akışı algoritmalarında kullanışlıdır.

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

Sıfırdan MaxHeap Uygulama

Bir MaxHeap, karşılaştırmayı tersine çevirir: parent, tüm alt düğümlerinden büyük veya onlara eşit olmalıdır. Yukarı ve aşağı süzmedeki karşılaştırmayı basitçe tersine çevirin. Alternatif olarak değerleri bir negatifleme sınıfına sarabilir veya Python'ın heapq kullanırken yaptığı gibi tamsayıları negatifleyebilirsiniz. Sıfırdan uygulamak, minimum ve maksimum yığınlarının yalnızca karşılaştırma işlecinin değiştiği özdeş yapılar olduğunu gösterir.

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]

Yığından Herhangi Bir Öğeyi Silme

Bir yığından rastgele bir öğeyi (kök olmayan bir öğeyi) silmek O(log n) maliyetindedir, ancak öğenin indeksinin bilinmesini gerektirir. Öğeyi son öğeyle değiştirin, son öğeyi kaldırın ve ardından yerine geçen öğeye yukarı veya aşağı süzme uygulayın (yığın özelliğini yalnızca bu yönlerden biri ihlal eder). Bu teknik, Dijkstra algoritmasında ertelenmiş silmeyle ve anahtarı azaltma işlemlerini destekleyen öncelik kuyruklarında kullanılır.

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

En Sık Görülen K Öğeyi Bulma

En Sık Görülen K Öğe problemi (LeetCode #347), k boyutunda bir minimum yığını kullanır. Her girdinin (frequency, element) biçiminde olduğu bir minimum yığınını koruyun. Her benzersiz öğeyi işleyin: yığında k'den az öğe varsa push edin; aksi hâlde yeni öğenin sıklığı yığındaki minimumdan büyükse minimumu pop edip yeni öğeyi push edin. Son yığın, O(n log k) time maliyetiyle en sık görülen k öğeyi içerir.

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]

Zamanlamada Yığın Uygulamaları

Yarışmalı programlamanın ötesinde, yığınlar gerçek dünyadaki zamanlama sistemlerinin temelini oluşturur. İşletim sistemi görev zamanlayıcıları, en yüksek önceliğe sahip hazır işlemi her zaman çalıştırmak için bir öncelik kuyruğu (yığın) kullanır. Olay güdümlü benzetimler, olay zamanına göre anahtarlanmış bir min-yığın kullanarak olayları zaman sırasıyla işler. Ağ paketi zamanlayıcıları, trafiğe hizmet kalitesi sınıfına göre öncelik verir. Yığını anlamak, tüm bu sistemler için zihinsel bir model edinmenizi sağlar ve kuyruklama ile zamanlama hakkındaki sistem tasarımı mülakatlarında doğal olarak karşınıza çıkar.

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

Hızlı Kontrol

Bu dersteki Veri Yapıları & Algoritmalar — Kodlama Mülakatı Hazırlığı kavramlarını ne kadar anladığınızı sınayın.

İnteraktif derste cevapla

Ders Özeti

Bu derste şunları öğrendiniz: yukarı süzme ve aşağı süzme işlemleriyle sıfırdan MinHeap ve MaxHeap oluşturmayı, neden tek tek O(n log n) eklemeden daha iyi olduğunu açıklayan Floyd'un O(n) heapify algoritmasını ve en sık görülen k öğe ile dizin üzerinden silme gibi pratik uygulamaları. Sırada Python'un heapq modülünü ve maks-yığın hilelerini inceleyeceğiz.

Başlamak ücretsiz

Yapay zeka eğitmeniyle Python öğren — ücretsiz

Tarayıcında gerçek kod yaz ve çalıştır, 7/24 yapay zeka eğitmeninden anında yardım al; web'de ya da uygulamada kaldığın yerden devam et.

Kurslar: 30
Dersler: 120

Ücretsiz öğrenmeye başla Tüm kursu görüntüle

Sıkça Sorulan Sorular

“Yığın Oluşturma, Ekleme ve Çıkarma İşlemlerini Sıfırdan Uygulama” dersi ücretsiz mi?

Evet — “Yığın Oluşturma, Ekleme ve Çıkarma İşlemlerini Sıfırdan Uygulama” dersin tüm metni burada web'de ücretsiz olarak okunabilir. Etkileşimli olarak pratik yapmak (yerleşik kod editörü ve 7/24 yapay zeka koçu) ve DSA Interview Prep kursunun geri kalanını açmak için CoddyKit PRO'ya yükselt. DSA Interview Prep kursu toplamda 4 dersten oluşur.

“Yığın Oluşturma, Ekleme ve Çıkarma İşlemlerini Sıfırdan Uygulama” dersinde ne öğreneceğim?

Ekleme için yukarı doğru, çıkarma için aşağı doğru yığın düzenleme işlemlerini uygulayın; ardından Floyd algoritmasıyla sıralanmamış bir diziden O(n) sürede yığın oluşturun. DSA Interview Prep ile uygulamalı kodu tarayıcıda doğrudan çalıştırarak pratik yaparsın ve 7/24 yapay zeka koçu dersi çalışırken sorularını yanıtlar.

DSA Interview Prep öğrenmeye başlamak için deneyim gerekli mi?

Önceden deneyim gerekmez. CoddyKit'te DSA Interview Prep, başlangıçtan ileri seviyeye kadar yapılandırıldığı için buradan başlayabilir veya başından başlayıp kendi hızında ilerleme yapabilirsin. Bu, 4 dersinin 2. dersidir.

“Yığın Oluşturma, Ekleme ve Çıkarma İşlemlerini Sıfırdan Uygulama” dersi ne kadar sürer?

Çoğu CoddyKit dersi yaklaşık 5–10 dakika sürer. Her biri kısa ve etkileşimli olduğu için sabit ilerleme yaparsın ve web ile uygulama arasında tam olarak bıraktığın yerden devam edebilirsin.

Bu DSA Interview Prep dersinde kod yazıp çalıştırabilir miyim?

Evet. Her DSA Interview Prep dersi yerleşik bir kod editörü içerir, bu sayede tarayıcıda gerçek kod yazıp çalıştırabilir ve anlık yapay zeka geri bildirimi alırsın — yerel kurulum gerekli değildir.

Bu kursun tüm dersleri

Yığın Özelliği ve Dizi Gösterimi
Yığın Oluşturma, Ekleme ve Çıkarma İşlemlerini Sıfırdan Uygulama
Python heapq ve Maksimum Yığın Taktikleri
Veri Akışından Medyan ve K-Yollu Birleştirme

← DSA Interview Prep Sayfasına Dön