0Pricing
DSA Interview Prep · Ders

Yığın Özelliği ve Dizi Gösterimi

Dizi olarak saklanan tam ikili ağaç yapısını anlayın, ebeveyn/çocuk dizin formüllerini çıkarın ve yukarı süzme ile aşağı süzme işlemlerini görselleştirin.

Yığın Özelliği ve Dizi Gösterimi, CoddyKit'te ücretsiz bir DSA Interview Prep dersidir. Bu, 4 dersinin 1. 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.

Yığın Nedir?

Bir yığın, yığın özelliğini sağlayan özel amaçlı bir tam ikili ağaçtır: bir minimum yığınında her parent düğümü çocuklarından küçük veya onlara eşittir; bir maksimum yığınında ise her parent düğümü çocuklarından büyük veya onlara eşittir. Bu özellik, minimum (veya maksimum) öğenin her zaman kökte bulunmasını garanti ederek uç öğeye O(1) maliyetle erişilmesini sağlar. Yığınlar, öncelik kuyruklarının temelindeki veri yapısıdır.

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

Tam İkili Ağaç Yapısı

Bir yığın, tam ikili ağaç olarak saklanır: son seviye dışındaki tüm seviyeler tamamen doldurulur; son seviye ise mümkünse soldan sağa doldurulur. Boşa alan veya işaretçi kullanmadan zarif bir dizi gösterimini mümkün kılan yapı budur. Tamlık özelliği, yığının yüksekliğinin her zaman floor(log₂ n) olmasını sağlar ve O(log n) maliyetli push ve pop işlemlerini garanti eder.

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

Yığının Dizi Gösterimi

Tam ikili ağaç yapısı, bir yığının işaretçi olmadan düz bir dizide saklanmasına olanak tanır. i indeksindeki (0'dan başlayan indeksleme) bir düğüm için parent düğümü (i-1) // 2 konumunda, sol çocuğu 2i+1 konumunda ve sağ çocuğu 2i+2 konumundadır. Bu tamsayı aritmetiği, işaretçilerle gezinmenin yerini alır ve yığınları önbellek kullanımı açısından son derece verimli hâle getirir.

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

Yukarı Süzme: Eklemeden Sonra Yığını Düzeltme

Yukarı süzme (kabarcıkla yukarı çıkarma veya yukarı doğru yığınlaştırma olarak da adlandırılır), yığın dizisinin sonuna yeni bir öğe eklendikten sonra kullanılır. Yeni öğeyi parent ile karşılaştırın; yığın özelliği ihlal ediliyorsa bu öğelerin yerlerini değiştirin ve yukarı doğru devam edin. Öğe doğru konuma gelene veya köke ulaşana kadar tekrarlayın. Ağaç yüksekliği O(log n) olduğundan bu işlem O(log n) maliyetindedir.

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

Aşağı Süzme: Pop Sonrası Yığını Düzeltme

Aşağı süzme (aşağı doğru yığınlaştırma), kök kaldırıldıktan sonra kullanılır. Son öğeyi köke taşıyın, ardından yığın özelliği yeniden sağlanana kadar bu öğeyi daha küçük çocukla (minimum yığını için) tekrar tekrar yer değiştirerek aşağı indirin. Bu işlem de O(log n) maliyetindedir. Yukarı ve aşağı süzme, tüm yığın işlemlerinin yapı taşlarıdır.

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

Diziden Yığın Oluşturma: Floyd Algoritması

n öğeyi tek tek ve basitçe eklemek O(n log n) maliyetindedir. Floyd'un heapify algoritması, son yaprak olmayan düğümden (indeks n//2 - 1) başlayıp köke doğru geriye ilerleyerek her yaprak olmayan düğüme aşağı süzme uygulamak suretiyle O(n) maliyetle bir yığın oluşturur. Yaprak düğümler zaten basit yığınlardır; bu nedenle yalnızca iç düğümleri düzeltmemiz gerekir. Toplam işin O(n) yerine O(n log n) olmamasının nedeni budur.

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

Dizi Yığını Kullanarak Yığın Sıralaması

Yığın sıralaması, O(1) ek alan kullanarak O(n log n) maliyetle çalışır. 1. aşama: diziden O(n) maliyetle bir maksimum yığını oluşturun. 2. aşama: kökü sıralanmamış son öğeyle yer değiştirerek maksimum değeri tekrar tekrar çıkarın, ardından küçültülmüş yığında aşağı süzme uygulayın. n çıkarma işleminden sonra dizi artan düzende sıralanmış olur. Bu yerinde algoritma, dizi gösteriminin ayrı bir veri yapısı ayırmadan sıralama yapmayı nasıl mümkün kıldığını gösterir.

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]

Minimum Yığını ve Maksimum Yığını Karşılaştırması

Bir minimum yığınının kökünde en küçük öğe bulunur; pop işlemi her zaman minimum değeri verir. Bir maksimum yığınının kökünde en büyük öğe bulunur; pop işlemi her zaman maksimum değeri verir. İkisinin de yapısı ve işlemleri aynıdır; yalnızca karşılaştırmanın yönü değişir. Python'ın heapq modülü yalnızca bir minimum yığını uygular; bu nedenle maksimum yığınını benzetmek için değerlerin işaretini tersine çevirmeniz gerekir.

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)

Yığın İşlemlerinin Karmaşıklık Özeti

Yığının tüm işlemleri, her ikisi de O(log n) olan yukarı ve aşağı süzme işlemlerinden türetilir. Push: append + yukarı süzme = O(log n). Pop: kökü son öğeyle değiştirme + aşağı süzme = O(log n). Peek: 0 indeksindeki öğeye erişim = O(1). Yığın oluşturma: Floyd algoritmasıyla O(n). Yığın sıralaması: O(n log n). Bu karmaşıklıklar, dinamik bir koleksiyondan minimum veya maksimum değere tekrar tekrar ihtiyaç duyduğunuzda yığınları ideal yapı hâline getirir.

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

Mülakatlarda Pratik Yığın Örüntüleri

Yığınlar, ortak bir örüntüye sahip bir dizi mülakat problemini çözer: n öğe veri akışı içinden geçerken k adaydan oluşan bir öncelik kuyruğunu korumak. En sık görülen k öğe, kökene en yakın k nokta ve görev zamanlayıcı problemlerinin tümü bu örüntüyü kullanır. Şunu gördüğünüzde bu örüntüyü tanıyın: 'n öğeden oluşan bir veri akışı verildiğinde, en iyi k öğeyi koruyun' — bu durumda her zaman k boyutunda bir yığın gerekir ve toplam maliyet O(n log k) olur.

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

Yığın ve Sıralı Dizi Arasındaki Tercihler

Yalnızca minimum veya maksimum değere tekrar tekrar erişmeniz gerekiyorsa ve koleksiyon dinamik olarak değişiyorsa bir yığın seçin. İndekse göre rastgele erişime veya aralık sorgularına ihtiyacınız varsa bir sıralı dizi seçin. Yığının zayıf yönü, rastgele öğeler için aramanın O(n) olmasıdır; güçlü yönü ise ekleme/silme işlemlerinin O(log n) ve minimum/maksimum değere erişimin O(1) olmasıdır. Sıralı dizide ekleme O(n) maliyetindedir, ancak ikili aramayla arama O(log n) maliyetindedir.

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

Hızlı Kontrol

Bu dersteki Veri Yapıları & Algoritmalar — Kodlama Mülakatına Hazırlık kavramlarını anlayıp anlamadığınızı sınayın.

Ders Özeti

Bu derste şunları öğrendiniz: yığın özelliğini ve tam ikili ağaç yapısını, parent/child indeks formülleriyle dizi gösterimini ve Floyd'un O(n) oluşturma yöntemi de dâhil olmak üzere tüm yığın işlemlerinin yapı taşları olan yukarı ve aşağı süzmeyi. Sırada heapify uygulayacak ve Python'ın heapq modülünü inceleyeceğiz.

Sıkça Sorulan Sorular

“Yığın Özelliği ve Dizi Gösterimi” dersi ücretsiz mi?

Evet — “Yığın Özelliği ve Dizi Gösterimi” 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 Özelliği ve Dizi Gösterimi” dersinde ne öğreneceğim?

Dizi olarak saklanan tam ikili ağaç yapısını anlayın, ebeveyn/çocuk dizin formüllerini çıkarın ve yukarı süzme ile aşağı süzme işlemlerini görselleştirin. 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 1. dersidir.

“Yığın Özelliği ve Dizi Gösterimi” 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

  1. Yığın Özelliği ve Dizi Gösterimi
  2. Yığın Oluşturma, Ekleme ve Çıkarma İşlemlerini Sıfırdan Uygulama
  3. Python heapq ve Maksimum Yığın Taktikleri
  4. Veri Akışından Medyan ve K-Yollu Birleştirme
← DSA Interview Prep Sayfasına Dön