Bottom-up heap बनाना और heapsort
संबंध और contract
मौजूदा “Binary min-heaps: complete shape and safe operations” में insertion और extract-min पढ़े हैं। उसी complete-tree shape और sift विचार का उपयोग करें; यहाँ नई बातें bottom-up build तथा sorting हैं। Zero-based A[0:n] में max-heap लें: children 2i+1,2i+2, active size h। हर parent अपने children से कम नहीं है।
1. नीचे से heap बनाएँ
floor(n/2) से n−1 तक leaves हैं, जो पहले से heaps हैं। i=floor(n/2)−1 से 0 तक reverse क्रम में size n के भीतर sift-down करें और बड़ा child चुनें। i process करने से पहले दोनों child subtrees heaps हैं। Sift चुने path के violations ठीक करके i का पूरा subtree heap बनाता है। यही reverse-index invariant है; arbitrary top-down sift से यह guarantee नहीं।
Sift-down: जब तक 2i+1<h, बड़े existing child का index c लें। A[i]>=A[c] हो तो stop; अन्यथा swap करके i=c करें। Equal children में consistent कोई भी choice मान्य है। h से छोटे indices ही active heap हैं।
हल किया build [1,4,3,2,5]: i=1 पर children 2,5 हैं; 4 को 5 से swap करके [1,5,3,2,4]। i=0 पर 1,5 swap: [5,1,3,2,4]; फिर 1,4 swap: [5,4,3,2,1]। Heap partial order है; siblings का क्रम तय नहीं और heap array sorted जरूरी नहीं।
2. Build linear क्यों है
हर node को O(log n) देना सही लेकिन loose O(n log n) bound है। अधिकतर nodes नीचे हैं। Height h के nodes अधिकतम O(n/2^(h+1)), प्रत्येक का sift cost O(h+1)। कुल O(n sum (h+1)/2^(h+1))=O(n), क्योंकि infinite series converges। इस implementation में Θ(n) internal nodes visit होने से Ω(n), अतः build Θ(n)। Repeated insertion अलग method है और उसका worst case O(n log n) है।
3. घटती boundary से sorting
Max-heap बनाएँ। end=n−1 से 1 तक: A[0],A[end] swap; h=end; केवल A[0:h] में root sift-down। हर iteration से पहले prefix max-heap, suffix ascending sorted और पहले निकले सबसे बड़े keys रखता है। बाकी maximum को end पर रखने से suffix बढ़ता है। Sift को sorted suffix में न जाने दें।
[5,4,3,2,1] में 5 को अंत में भेजकर repair: [4,2,3,1 | 5]। अगला [3,2,1 | 4,5], फिर [2,1 | 3,4,5], अंत [1 | 2,3,4,5]। Bar heap boundary है। इस scheme में max-heap ascending और min-heap descending result देता है।
4. लागत और गलतियाँ
Worst-case total Θ(n log n): linear build और n−1 logarithmic-upper-bound extractions; worst-case inputs bound attain करते हैं। Iterative sift-down से auxiliary storage O(1), recursive stack नहीं। Standard heapsort unstable है: [2a,2b,1] पहले max-heap है; swaps से [1,2b,2a] मिल सकता है।
Linear build को linear sorting न मानें। Repeated insertion bottom-up build नहीं। Heap invariant sorted order से कमजोर है। Height leaf तक नीचे की दूरी, depth root से दूरी है; build sum में depth लगाने से गलत intuition बनती है।
मौलिक अभ्यास: छह single-correct MCQ
ये मौलिक शिक्षण प्रश्न हैं, पिछले वर्षों के प्रश्न नहीं। ठीक एक उत्तर चुनें।
P01. Size 10 zero-based heap का अंतिम internal index?
A. 4 B. 5 C. 9 D. 10
उत्तर: A
A: floor(10/2)−1=4।
B: 5 leaf है।
C: 9 leaf है।
D: 10 array से बाहर है।
P02. Bottom-up build का worst-case time?
A. Θ(log n) B. Θ(n) C. Θ(n log n) D. Θ(n²)
उत्तर: B
A: Linear nodes process होंगे।
B: Height-weighted sum linear है।
C: O(n log n) loose upper bound है, लेकिन Θ(n log n) tight running time नहीं है।
D: Quadratic work नहीं चाहिए।
P03. [1,4,3,2,5] का बताया bottom-up max-heap:
A. [1,2,3,4,5] B. [5,4,3,2,1] C. [5,1,3,2,4] D. [4,5,3,2,1]
उत्तर: B
A: यह max-heap नहीं।
B: बताया sift sequence यही देता है।
C: Node 1 का child 4 बड़ा है।
D: Root 4 से child 5 बड़ा है।
P04. Maximum को A[end] में रखने के बाद repair indices?
A. 0 से end B. 0 से end−1 C. end से n−1 D. हमेशा पूरे n
उत्तर: B
A: Sorted suffix का entry शामिल है।
B: नया heap size end है।
C: Suffix final है।
D: Sorted entries बिगड़ सकते हैं।
P05. Iterative in-array heapsort extra space?
A. Θ(1) B. Θ(log n) C. Θ(n) D. Θ(n²)
उत्तर: A
A: Constant indices और swap storage है।
B: Recursive stack नहीं।
C: Output buffer नहीं।
D: Matrix नहीं।
P06. Standard heapsort में किसकी guarantee नहीं?
A. Max-heap scheme से ascending output B. Worst-case O(n log n) C. Equal records का क्रम D. Constant extra array storage
उत्तर: C
A: Suffix invariant ascending output देता है।
B: यह worst-case bound सही है।
C: Swaps equal records उलट सकते हैं।
D: Iterative sift constant storage देता है।
स्रोत और दायरा
यह 2026 course के बताए भाग का पाठ है, पूरे Algorithms syllabus की समाप्ति नहीं। सभी गणनात्मक उदाहरण और प्रश्न मौलिक हैं। 2027 की पूर्णता का दावा नहीं।
प्रगति सहेजने के लिए साइन इन करें। साइन इन