Heap, priority queue ve heapsort

Binary heap complete binary tree biçimini ve heap order'ı birlikte korur. Min-heap'te ebeveyn≤çocuk; bütün sol alt ağaç küçük, sağ alt ağaç büyük olmak zorunda değildir. Bu BST değildir. Sıfır tabanlı dizide çocuklar 2i+1,2i+2, parent (i−1)//2'dir.

Ekleme sona koyup sift-up yapar; minimum çıkarma kökü son öğeyle değiştirip sift-down yapar. Arbitrary key araması heap'te O(n) olabilir. Decrease-key için öğenin konumunu takip eden ek map gerekir; basit heapq uygulamalarında eski entry'leri stale olarak atlayan yaklaşım kullanılabilir.

Bottom-up heapify Θ(n)'dir: düğümlerin çoğu yaprağa yakındır ve az aşağı iner. “Her düğüm log n iner” üst sınırı gevşektir. Heapsort max-heap kökünü sona taşır ve aktif heap'i daraltır; O(n log n) ve O(1) yardımcı alanlı in-place varyant stabil değildir. Öncelikleri eşitse tie-breaker eklemek karma nesneleri yanlış karşılaştırmayı önler.

import heapq
jobs = [(3, "C"), (1, "A"), (2, "B")]
heapq.heapify(jobs)
order = [heapq.heappop(jobs)[1] for _ in range(3)]
assert order == ["A", "B", "C"]