"use strict"; const {Fragment: _Fragment, jsx: _jsx, jsxs: _jsxs} = arguments[0]; const {useMDXComponents: _provideComponents} = arguments[0]; function _createMdxContent(props) { const _components = { code: "code", em: "em", h3: "h3", li: "li", ol: "ol", p: "p", pre: "pre", span: "span", strong: "strong", table: "table", tbody: "tbody", td: "td", th: "th", thead: "thead", tr: "tr", ul: "ul", ..._provideComponents(), ...props.components }, {Analogy, Answer, Applications, Assessment, CodeBlock, ComparisonTable, ContentAttribution, DefinitionEntry, DefinitionGroup, English, Explanation, FormulaBox, Hinglish, ImportantQA, KeyPoints, MCQ, Practical, Prompt, QAQuestion, Remember, Step, StepByStep, SubTopicHeader, Theory, TopicOverview} = _components; if (!Analogy) _missingMdxReference("Analogy", true); if (!Answer) _missingMdxReference("Answer", true); if (!Applications) _missingMdxReference("Applications", true); if (!Assessment) _missingMdxReference("Assessment", true); if (!CodeBlock) _missingMdxReference("CodeBlock", true); if (!ComparisonTable) _missingMdxReference("ComparisonTable", true); if (!ContentAttribution) _missingMdxReference("ContentAttribution", true); if (!DefinitionEntry) _missingMdxReference("DefinitionEntry", true); if (!DefinitionGroup) _missingMdxReference("DefinitionGroup", true); if (!English) _missingMdxReference("English", true); if (!Explanation) _missingMdxReference("Explanation", true); if (!FormulaBox) _missingMdxReference("FormulaBox", true); if (!Hinglish) _missingMdxReference("Hinglish", true); if (!ImportantQA) _missingMdxReference("ImportantQA", true); if (!KeyPoints) _missingMdxReference("KeyPoints", true); if (!MCQ) _missingMdxReference("MCQ", true); if (!Practical) _missingMdxReference("Practical", true); if (!Prompt) _missingMdxReference("Prompt", true); if (!QAQuestion) _missingMdxReference("QAQuestion", true); if (!Remember) _missingMdxReference("Remember", true); if (!Step) _missingMdxReference("Step", true); if (!StepByStep) _missingMdxReference("StepByStep", true); if (!SubTopicHeader) _missingMdxReference("SubTopicHeader", true); if (!Theory) _missingMdxReference("Theory", true); if (!TopicOverview) _missingMdxReference("TopicOverview", true); return _jsxs(_Fragment, { children: [_jsxs(Theory, { children: [_jsx(SubTopicHeader, { id: "6.3", title: "Expression Tree and Heap" }), _jsxs(TopicOverview, { title: "Expression Tree and Heap", topicId: "6.3", readingTime: "12 min read", difficulty: "Medium", children: [_jsx(English, { children: _jsxs(_components.p, { children: ["Trees are incredibly versatile data structures, and two of their most powerful applications are ", _jsx(_components.strong, { children: "Expression Trees" }), " and ", _jsx(_components.strong, { children: "Heaps" }), ". An Expression Tree represents a mathematical expression in a tree form where operators are internal nodes and operands are leaves — making it easy to evaluate, convert between notation formats (infix, prefix, postfix), and optimize expressions. A Heap, on the other hand, is a special complete binary tree that satisfies the heap property — it is the backbone of priority queues, efficient sorting (Heap Sort), and many algorithmic solutions. In this subtopic, we will explore both concepts in depth, understand how to build and use them, and see their real-world applications."] }) }), _jsx(Hinglish, { children: _jsxs(_components.p, { children: ["Trees bahut versatile data structures hain, aur unke do sabse powerful applications hain — ", _jsx(_components.strong, { children: "Expression Tree" }), " aur ", _jsx(_components.strong, { children: "Heap" }), ". Expression Tree ek mathematical expression ko tree form mein represent karta hai jahan operators internal nodes hote hain aur operands leaves hote hain — isse evaluate karna, notations (infix, prefix, postfix) ke beech convert karna, aur expressions ko optimize karna bahut easy ho jaata hai. Heap ek special complete binary tree hai jo heap property satisfy karta hai — yeh priority queues, efficient sorting (Heap Sort), aur bahut se algorithmic solutions ki backbone hai. Is subtopic mein hum dono concepts ko depth mein samjhenge, banana aur use karna seekhenge, aur unki real-world applications dekhenge."] }) })] }), _jsxs(DefinitionGroup, { children: [_jsxs(DefinitionEntry, { term: "Expression Tree", children: [_jsx(English, { children: _jsxs(_components.p, { children: ["An ", _jsx(_components.strong, { children: "Expression Tree" }), " is a binary tree used to represent a mathematical expression. In this tree, every ", _jsx(_components.strong, { children: "leaf node" }), " is an operand (a number or variable), and every ", _jsx(_components.strong, { children: "internal node" }), " is an operator (like +, -, *, /). The tree structure naturally captures the precedence and associativity of operations, making expression evaluation and conversion between infix, prefix, and postfix notations straightforward."] }) }), _jsx(Hinglish, { children: _jsxs(_components.p, { children: [_jsx(_components.strong, { children: "Expression Tree" }), " ek binary tree hai jo mathematical expression ko represent karne ke liye use hota hai. Is tree mein har ", _jsx(_components.strong, { children: "leaf node" }), " ek operand hota hai (number ya variable), aur har ", _jsx(_components.strong, { children: "internal node" }), " ek operator hota hai (jaise +, -, *, /). Tree ki structure naturally operations ki precedence aur associativity ko capture karti hai, jisse expression evaluate karna aur infix, prefix, postfix notations ke beech convert karna straightforward ho jaata hai."] }) })] }), _jsxs(DefinitionEntry, { term: "Heap", children: [_jsx(English, { children: _jsxs(_components.p, { children: ["A ", _jsx(_components.strong, { children: "Heap" }), " is a specialized complete binary tree that satisfies the ", _jsx(_components.strong, { children: "heap property" }), ". It is most commonly implemented using an array (not pointers), where the parent-child relationships are maintained through index calculations. Heaps are of two types — Min Heap and Max Heap — and they form the foundation of priority queues and Heap Sort."] }) }), _jsx(Hinglish, { children: _jsxs(_components.p, { children: [_jsx(_components.strong, { children: "Heap" }), " ek specialized complete binary tree hai jo ", _jsx(_components.strong, { children: "heap property" }), " satisfy karta hai. Ise most commonly array se implement kiya jaata hai (pointers se nahi), jahan parent-child relationships index calculations ke through maintain hoti hain. Heap do tarah ke hote hain — Min Heap aur Max Heap — aur yeh priority queues aur Heap Sort ki foundation hote hain."] }) })] }), _jsxs(DefinitionEntry, { term: "Min Heap", children: [_jsx(English, { children: _jsxs(_components.p, { children: ["A ", _jsx(_components.strong, { children: "Min Heap" }), " is a heap where the value of every parent node is ", _jsx(_components.strong, { children: "less than or equal to" }), " the values of its children. This guarantees that the ", _jsx(_components.strong, { children: "smallest element" }), " is always at the root. It is useful when you need quick access to the minimum element, such as in a priority queue where the highest priority item should be processed first."] }) }), _jsx(Hinglish, { children: _jsxs(_components.p, { children: [_jsx(_components.strong, { children: "Min Heap" }), " ek heap hai jahan har parent node ki value uske children ki values se ", _jsx(_components.strong, { children: "chhoti ya barabar" }), " hoti hai. Isse guarantee milti hai ki ", _jsx(_components.strong, { children: "sabse chhota element" }), " hamesha root par hota hai. Yeh tab useful hota hai jab minimum element ki quick access chahiye, jaise priority queue mein jahan sabse pehle highest priority item process karna hota hai."] }) })] }), _jsxs(DefinitionEntry, { term: "Max Heap", children: [_jsx(English, { children: _jsxs(_components.p, { children: ["A ", _jsx(_components.strong, { children: "Max Heap" }), " is a heap where the value of every parent node is ", _jsx(_components.strong, { children: "greater than or equal to" }), " the values of its children. This guarantees that the ", _jsx(_components.strong, { children: "largest element" }), " is always at the root. It is useful when you need quick access to the maximum element — for example, finding the largest task by priority or implementing Heap Sort in ascending order."] }) }), _jsx(Hinglish, { children: _jsxs(_components.p, { children: [_jsx(_components.strong, { children: "Max Heap" }), " ek heap hai jahan har parent node ki value uske children ki values se ", _jsx(_components.strong, { children: "badi ya barabar" }), " hoti hai. Isse guarantee milti hai ki ", _jsx(_components.strong, { children: "sabse bada element" }), " hamesha root par hota hai. Yeh tab useful hota hai jab maximum element ki quick access chahiye — for example, priority ke hisaab se bada task dhoondna ya ascending order mein Heap Sort implement karna."] }) })] }), _jsxs(DefinitionEntry, { term: "Heapify", children: [_jsx(English, { children: _jsxs(_components.p, { children: [_jsx(_components.strong, { children: "Heapify" }), " is the process of rearranging elements in a heap to restore the heap property after it has been violated. When a node's value breaks the heap order (e.g., a parent is smaller than its child in a Max Heap), heapify compares the node with its children and swaps it with the largest (or smallest, in Min Heap) child, then recursively applies the same process downward until the property is restored."] }) }), _jsx(Hinglish, { children: _jsxs(_components.p, { children: [_jsx(_components.strong, { children: "Heapify" }), " ek process hai jisme elements ko heap mein rearrange kiya jaata hai taaki heap property restore ho sake jab woh violate ho jaaye. Jab kisi node ki value heap order todeti hai (jaise Max Heap mein parent chhota hai apne child se), heapify node ko uske children se compare karta hai aur largest (ya Min Heap mein smallest) child ke saath swap karta hai, phir recursively neeche ki taraf same process apply karta hai jab tak property restore na ho jaaye."] }) })] }), _jsxs(DefinitionEntry, { term: "Complete Binary Tree", children: [_jsx(English, { children: _jsxs(_components.p, { children: ["A ", _jsx(_components.strong, { children: "Complete Binary Tree" }), " is a binary tree in which every level is completely filled except possibly the last level, which is filled from left to right. This property is critical for heaps because it allows them to be efficiently represented as arrays without wasting space — there are no gaps in the array representation."] }) }), _jsx(Hinglish, { children: _jsxs(_components.p, { children: [_jsx(_components.strong, { children: "Complete Binary Tree" }), " ek binary tree hai jismein har level completely filled hota hai, except possibly last level, jo left to right se fill hota hai. Yeh property heaps ke liye critical hai kyunki isse array se efficiently represent kiya ja sakta hai bina space waste kiye — array representation mein koi gaps nahi hoti."] }) })] })] }), _jsxs(Explanation, { children: [_jsxs(English, { children: [_jsx(_components.h3, { children: "🌳 What is an Expression Tree?" }), _jsxs(_components.p, { children: ["An ", _jsx(_components.strong, { children: "Expression Tree" }), " is a binary tree that visually and structurally represents a mathematical expression. Think of it as a family tree for a math equation — operators are the \"parents\" and operands are the \"children.\" The key insight is that the ", _jsx(_components.strong, { children: "structure of the tree encodes the order of operations" }), ", so there is never any ambiguity about which operation should be performed first."] }), _jsxs(_components.p, { children: ["For example, consider the infix expression ", _jsx(_components.span, { className: "katex", children: _jsxs(_components.span, { className: "katex-html", "aria-hidden": "true", children: [_jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mopen", children: "(" }), _jsx(_components.span, { className: "mord", children: "3" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2222em" } }), _jsx(_components.span, { className: "mbin", children: "+" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2222em" } })] }), _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mord", children: "4" }), _jsx(_components.span, { className: "mclose", children: ")" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2222em" } }), _jsx(_components.span, { className: "mbin", children: "×" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2222em" } })] }), _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mopen", children: "(" }), _jsx(_components.span, { className: "mord", children: "5" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2222em" } }), _jsx(_components.span, { className: "mbin", children: "−" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2222em" } })] }), _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mord", children: "2" }), _jsx(_components.span, { className: "mclose", children: ")" })] })] }) }), ". In this expression:"] }), _jsxs(_components.ul, { children: ["\n", _jsxs(_components.li, { children: [_jsx(_components.code, { children: "+" }), " adds ", _jsx(_components.code, { children: "3" }), " and ", _jsx(_components.code, { children: "4" })] }), "\n", _jsxs(_components.li, { children: [_jsx(_components.code, { children: "-" }), " subtracts ", _jsx(_components.code, { children: "2" }), " from ", _jsx(_components.code, { children: "5" })] }), "\n", _jsxs(_components.li, { children: [_jsx(_components.code, { children: "*" }), " multiplies the results of the two sub-expressions"] }), "\n"] }), _jsxs(_components.p, { children: ["The Expression Tree for this would place ", _jsx(_components.code, { children: "*" }), " at the root, ", _jsx(_components.code, { children: "+" }), " and ", _jsx(_components.code, { children: "-" }), " as its children, and the numbers as leaf nodes. This tree structure makes it trivial to evaluate the expression — just evaluate left subtree, evaluate right subtree, and apply the root operator."] })] }), _jsxs(Hinglish, { children: [_jsx(_components.h3, { children: "🌳 Expression Tree Kya Hai?" }), _jsxs(_components.p, { children: [_jsx(_components.strong, { children: "Expression Tree" }), " ek binary tree hai jo ek mathematical expression ko visually aur structurally represent karta hai. Ise ek math equation ka family tree samajh lo — operators \"parents\" hote hain aur operands \"children\" hote hain. Key insight yeh hai ki ", _jsx(_components.strong, { children: "tree ki structure operation ka order encode karti hai" }), ", toh kabhi ambiguity nahi hoti ki kaunsa operation pehle perform karna hai."] }), _jsxs(_components.p, { children: ["For example, infix expression ", _jsx(_components.span, { className: "katex", children: _jsxs(_components.span, { className: "katex-html", "aria-hidden": "true", children: [_jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mopen", children: "(" }), _jsx(_components.span, { className: "mord", children: "3" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2222em" } }), _jsx(_components.span, { className: "mbin", children: "+" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2222em" } })] }), _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mord", children: "4" }), _jsx(_components.span, { className: "mclose", children: ")" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2222em" } }), _jsx(_components.span, { className: "mbin", children: "×" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2222em" } })] }), _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mopen", children: "(" }), _jsx(_components.span, { className: "mord", children: "5" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2222em" } }), _jsx(_components.span, { className: "mbin", children: "−" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2222em" } })] }), _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mord", children: "2" }), _jsx(_components.span, { className: "mclose", children: ")" })] })] }) }), " ko consider karo. Is expression mein:"] }), _jsxs(_components.ul, { children: ["\n", _jsxs(_components.li, { children: [_jsx(_components.code, { children: "+" }), " se ", _jsx(_components.code, { children: "3" }), " aur ", _jsx(_components.code, { children: "4" }), " add hota hai"] }), "\n", _jsxs(_components.li, { children: [_jsx(_components.code, { children: "-" }), " se ", _jsx(_components.code, { children: "5" }), " mein se ", _jsx(_components.code, { children: "2" }), " subtract hota hai"] }), "\n", _jsxs(_components.li, { children: [_jsx(_components.code, { children: "*" }), " se dono sub-expressions ke results multiply hote hain"] }), "\n"] }), _jsxs(_components.p, { children: ["Iska Expression Tree ", _jsx(_components.code, { children: "*" }), " ko root par rakhega, ", _jsx(_components.code, { children: "+" }), " aur ", _jsx(_components.code, { children: "-" }), " ko uske children ke roop mein, aur numbers ko leaf nodes ke roop mein. Yeh tree structure expression evaluate karna bahut easy bana deta hai — bas left subtree evaluate karo, right subtree evaluate karo, aur root operator apply karo."] })] }), _jsx(Analogy, { children: _jsxs(_components.p, { children: [_jsx(_components.strong, { children: "Expression Tree as a Decision Hierarchy:" }), " Imagine you're planning a road trip with friends. You need to decide: \"Should we go to the mountains OR the beach?\" (this is the root decision). If mountains — \"Should we camp OR stay in a hotel?\" If beach — \"Should we surf OR just relax?\" Each decision leads to sub-decisions, just like operators lead to sub-expressions. The final choices (camp, hotel, surf, relax) are your operands — the actual actions. The Expression Tree organizes this entire decision hierarchy so you can follow it from top to bottom and arrive at your final answer."] }) }), _jsxs(English, { children: [_jsx(_components.h3, { children: "🔄 Types of Expression Notations" }), _jsx(_components.p, { children: "The same expression can be written in three different notations, and each corresponds to a specific tree traversal:" }), _jsxs(_components.table, { children: [_jsx(_components.thead, { children: _jsxs(_components.tr, { children: [_jsx(_components.th, { style: { textAlign: "left" }, children: "Notation" }), _jsx(_components.th, { style: { textAlign: "left" }, children: "Format" }), _jsxs(_components.th, { style: { textAlign: "left" }, children: ["Example for ", _jsx(_components.span, { className: "katex", children: _jsxs(_components.span, { className: "katex-html", "aria-hidden": "true", children: [_jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mopen", children: "(" }), _jsx(_components.span, { className: "mord", children: "3" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2222em" } }), _jsx(_components.span, { className: "mbin", children: "+" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2222em" } })] }), _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mord", children: "4" }), _jsx(_components.span, { className: "mclose", children: ")" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2222em" } }), _jsx(_components.span, { className: "mbin", children: "×" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2222em" } })] }), _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mopen", children: "(" }), _jsx(_components.span, { className: "mord", children: "5" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2222em" } }), _jsx(_components.span, { className: "mbin", children: "−" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2222em" } })] }), _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mord", children: "2" }), _jsx(_components.span, { className: "mclose", children: ")" })] })] }) })] })] }) }), _jsxs(_components.tbody, { children: [_jsxs(_components.tr, { children: [_jsx(_components.td, { style: { textAlign: "left" }, children: _jsx(_components.strong, { children: "Infix" }) }), _jsx(_components.td, { style: { textAlign: "left" }, children: "operator between operands" }), _jsxs(_components.td, { style: { textAlign: "left" }, children: [_jsx(_components.code, { children: "3 + 4 * 5 - 2" }), " (with parentheses)"] })] }), _jsxs(_components.tr, { children: [_jsx(_components.td, { style: { textAlign: "left" }, children: _jsx(_components.strong, { children: "Prefix (Polish)" }) }), _jsx(_components.td, { style: { textAlign: "left" }, children: "operator before operands" }), _jsx(_components.td, { style: { textAlign: "left" }, children: _jsx(_components.code, { children: "* + 3 4 - 5 2" }) })] }), _jsxs(_components.tr, { children: [_jsx(_components.td, { style: { textAlign: "left" }, children: _jsx(_components.strong, { children: "Postfix (Reverse Polish)" }) }), _jsx(_components.td, { style: { textAlign: "left" }, children: "operator after operands" }), _jsx(_components.td, { style: { textAlign: "left" }, children: _jsx(_components.code, { children: "3 4 + 5 2 - *" }) })] })] })] }), _jsxs(_components.p, { children: ["The magic of Expression Trees is that a ", _jsx(_components.strong, { children: "single tree" }), " can produce all three notations through different traversals:"] }), _jsxs(_components.ul, { children: ["\n", _jsxs(_components.li, { children: [_jsx(_components.strong, { children: "In-Order Traversal" }), " (Left → Node → Right) gives ", _jsx(_components.strong, { children: "Infix" })] }), "\n", _jsxs(_components.li, { children: [_jsx(_components.strong, { children: "Pre-Order Traversal" }), " (Node → Left → Right) gives ", _jsx(_components.strong, { children: "Prefix" })] }), "\n", _jsxs(_components.li, { children: [_jsx(_components.strong, { children: "Post-Order Traversal" }), " (Left → Right → Node) gives ", _jsx(_components.strong, { children: "Postfix" })] }), "\n"] })] }), _jsxs(Hinglish, { children: [_jsx(_components.h3, { children: "🔄 Expression Notations Ke Types" }), _jsx(_components.p, { children: "Wohi expression teen different notations mein likha ja sakta hai, aur har notation ek specific tree traversal se milta hai:" }), _jsxs(_components.table, { children: [_jsx(_components.thead, { children: _jsxs(_components.tr, { children: [_jsx(_components.th, { style: { textAlign: "left" }, children: "Notation" }), _jsx(_components.th, { style: { textAlign: "left" }, children: "Format" }), _jsxs(_components.th, { style: { textAlign: "left" }, children: ["Example for ", _jsx(_components.span, { className: "katex", children: _jsxs(_components.span, { className: "katex-html", "aria-hidden": "true", children: [_jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mopen", children: "(" }), _jsx(_components.span, { className: "mord", children: "3" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2222em" } }), _jsx(_components.span, { className: "mbin", children: "+" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2222em" } })] }), _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mord", children: "4" }), _jsx(_components.span, { className: "mclose", children: ")" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2222em" } }), _jsx(_components.span, { className: "mbin", children: "×" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2222em" } })] }), _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mopen", children: "(" }), _jsx(_components.span, { className: "mord", children: "5" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2222em" } }), _jsx(_components.span, { className: "mbin", children: "−" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2222em" } })] }), _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mord", children: "2" }), _jsx(_components.span, { className: "mclose", children: ")" })] })] }) })] })] }) }), _jsxs(_components.tbody, { children: [_jsxs(_components.tr, { children: [_jsx(_components.td, { style: { textAlign: "left" }, children: _jsx(_components.strong, { children: "Infix" }) }), _jsx(_components.td, { style: { textAlign: "left" }, children: "operator operands ke beech" }), _jsxs(_components.td, { style: { textAlign: "left" }, children: [_jsx(_components.code, { children: "3 + 4 * 5 - 2" }), " (parentheses ke saath)"] })] }), _jsxs(_components.tr, { children: [_jsx(_components.td, { style: { textAlign: "left" }, children: _jsx(_components.strong, { children: "Prefix (Polish)" }) }), _jsx(_components.td, { style: { textAlign: "left" }, children: "operator operands se pehle" }), _jsx(_components.td, { style: { textAlign: "left" }, children: _jsx(_components.code, { children: "* + 3 4 - 5 2" }) })] }), _jsxs(_components.tr, { children: [_jsx(_components.td, { style: { textAlign: "left" }, children: _jsx(_components.strong, { children: "Postfix (Reverse Polish)" }) }), _jsx(_components.td, { style: { textAlign: "left" }, children: "operator operands ke baad" }), _jsx(_components.td, { style: { textAlign: "left" }, children: _jsx(_components.code, { children: "3 4 + 5 2 - *" }) })] })] })] }), _jsxs(_components.p, { children: ["Expression Trees ki magic yeh hai ki ", _jsx(_components.strong, { children: "ek hi tree" }), " teeno notations produce kar sakta hai different traversals se:"] }), _jsxs(_components.ul, { children: ["\n", _jsxs(_components.li, { children: [_jsx(_components.strong, { children: "In-Order Traversal" }), " (Left → Node → Right) → ", _jsx(_components.strong, { children: "Infix" }), " milta hai"] }), "\n", _jsxs(_components.li, { children: [_jsx(_components.strong, { children: "Pre-Order Traversal" }), " (Node → Left → Right) → ", _jsx(_components.strong, { children: "Prefix" }), " milta hai"] }), "\n", _jsxs(_components.li, { children: [_jsx(_components.strong, { children: "Post-Order Traversal" }), " (Left → Right → Node) → ", _jsx(_components.strong, { children: "Postfix" }), " milta hai"] }), "\n"] })] }), _jsx(Remember, { title: "Traversal-Notation Mapping", children: _jsxs(_components.ul, { children: ["\n", _jsxs(_components.li, { children: [_jsx(_components.strong, { children: "In-Order" }), " → ", _jsx(_components.strong, { children: "In-Fix" }), " (Both start with \"In\" — easy to remember!)"] }), "\n", _jsxs(_components.li, { children: [_jsx(_components.strong, { children: "Pre-Order" }), " → ", _jsx(_components.strong, { children: "Pre-Fix" }), " (Both start with \"Pre\")"] }), "\n", _jsxs(_components.li, { children: [_jsx(_components.strong, { children: "Post-Order" }), " → ", _jsx(_components.strong, { children: "Post-Fix" }), " (Both start with \"Post\")\r\nThis mapping is very commonly asked in exams!"] }), "\n"] }) }), _jsxs(English, { children: [_jsx(_components.h3, { children: "🛠️ Building an Expression Tree from Postfix" }), _jsxs(_components.p, { children: ["The most efficient way to build an Expression Tree is from a ", _jsx(_components.strong, { children: "postfix expression" }), " using a ", _jsx(_components.strong, { children: "stack-based algorithm" }), ". The algorithm is simple:"] }), _jsxs(_components.ol, { children: ["\n", _jsx(_components.li, { children: "Scan the postfix expression from left to right" }), "\n", _jsxs(_components.li, { children: ["If the current character is an ", _jsx(_components.strong, { children: "operand" }), " (number or variable), create a new node and push it onto the stack"] }), "\n", _jsxs(_components.li, { children: ["If the current character is an ", _jsx(_components.strong, { children: "operator" }), ", create a new node, then ", _jsx(_components.strong, { children: "pop two nodes" }), " from the stack — the first popped node becomes the ", _jsx(_components.strong, { children: "right child" }), " and the second becomes the ", _jsx(_components.strong, { children: "left child" }), " — then push the operator node back onto the stack"] }), "\n", _jsxs(_components.li, { children: ["After scanning all characters, the stack will contain exactly one node — which is the ", _jsx(_components.strong, { children: "root" }), " of the Expression Tree"] }), "\n"] }), _jsxs(_components.p, { children: [_jsx(_components.strong, { children: "Why does this work?" }), " Because in postfix notation, operands appear before their operators. So when we encounter an operator, its operands (which are already subtrees on the stack) are ready to be attached as children."] })] }), _jsxs(Hinglish, { children: [_jsx(_components.h3, { children: "🛠️ Postfix Se Expression Tree Kaise Banayein?" }), _jsxs(_components.p, { children: ["Expression Tree banane ka sabse efficient way hai ", _jsx(_components.strong, { children: "postfix expression" }), " se using a ", _jsx(_components.strong, { children: "stack-based algorithm" }), ". Algorithm simple hai:"] }), _jsxs(_components.ol, { children: ["\n", _jsx(_components.li, { children: "Postfix expression ko left to right scan karo" }), "\n", _jsxs(_components.li, { children: ["Agar current character ek ", _jsx(_components.strong, { children: "operand" }), " hai (number ya variable), toh ek naya node banao aur stack par push karo"] }), "\n", _jsxs(_components.li, { children: ["Agar current character ek ", _jsx(_components.strong, { children: "operator" }), " hai, toh ek naya node banao, phir stack se ", _jsx(_components.strong, { children: "do nodes pop karo" }), " — pehla popped node ", _jsx(_components.strong, { children: "right child" }), " banega aur doosra ", _jsx(_components.strong, { children: "left child" }), " banega — phir operator node ko wapas stack par push karo"] }), "\n", _jsxs(_components.li, { children: ["Saare characters scan karne ke baad, stack mein exactly ek node rahega — jo tree ka ", _jsx(_components.strong, { children: "root" }), " hoga"] }), "\n"] }), _jsxs(_components.p, { children: [_jsx(_components.strong, { children: "Yeh kyun kaam karta hai?" }), " Kyunki postfix notation mein operands unke operators se pehle aate hain. Toh jab hum operator encounter karte hain, uske operands (jo stack par already subtrees hain) ready hain children ke roop mein attach hone ke liye."] })] }), _jsxs(StepByStep, { title: "Building Expression Tree from Postfix: 34+52-*", children: [_jsx(Step, { title: "Postfix Expression", children: _jsxs(_components.p, { children: ["We want to build the tree for the postfix expression ", _jsx(_components.code, { children: "34+52-*" }), ", which represents ", _jsx(_components.span, { className: "katex", children: _jsxs(_components.span, { className: "katex-html", "aria-hidden": "true", children: [_jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mopen", children: "(" }), _jsx(_components.span, { className: "mord", children: "3" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2222em" } }), _jsx(_components.span, { className: "mbin", children: "+" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2222em" } })] }), _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mord", children: "4" }), _jsx(_components.span, { className: "mclose", children: ")" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2222em" } }), _jsx(_components.span, { className: "mbin", children: "×" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2222em" } })] }), _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mopen", children: "(" }), _jsx(_components.span, { className: "mord", children: "5" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2222em" } }), _jsx(_components.span, { className: "mbin", children: "−" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2222em" } })] }), _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mord", children: "2" }), _jsx(_components.span, { className: "mclose", children: ")" })] })] }) }), "."] }) }), _jsx(Step, { title: "Read '3' — Operand", children: _jsxs(_components.p, { children: ["Create node(3), push onto stack. Stack: ", _jsx(_components.code, { children: "[3]" })] }) }), _jsx(Step, { title: "Read '4' — Operand", children: _jsxs(_components.p, { children: ["Create node(4), push onto stack. Stack: ", _jsx(_components.code, { children: "[3, 4]" })] }) }), _jsx(Step, { title: "Read '+' — Operator", children: _jsxs(_components.p, { children: ["Pop node(4) → right child. Pop node(3) → left child. Create node(+) with these children. Push node(+). Stack: ", _jsx(_components.code, { children: "[+]" })] }) }), _jsx(Step, { title: "Read '5' — Operand", children: _jsxs(_components.p, { children: ["Create node(5), push onto stack. Stack: ", _jsx(_components.code, { children: "[+, 5]" })] }) }), _jsx(Step, { title: "Read '2' — Operand", children: _jsxs(_components.p, { children: ["Create node(2), push onto stack. Stack: ", _jsx(_components.code, { children: "[+, 5, 2]" })] }) }), _jsx(Step, { title: "Read '-' — Operator", children: _jsxs(_components.p, { children: ["Pop node(2) → right child. Pop node(5) → left child. Create node(-) with these children. Push node(-). Stack: ", _jsx(_components.code, { children: "[+, -]" })] }) }), _jsx(Step, { title: "Read '*' — Operator", children: _jsxs(_components.p, { children: ["Pop node(-) → right child. Pop node(+) → left child. Create node(", _jsx(_components.em, { children: ") with these children. Push node(" }), "). Stack: ", _jsx(_components.code, { children: "[*]" })] }) }), _jsx(Step, { title: "Result", children: _jsxs(_components.p, { children: ["Stack has one node: ", _jsx(_components.code, { children: "*" }), " (root). The complete tree is built! Evaluate: ", _jsx(_components.span, { className: "katex", children: _jsxs(_components.span, { className: "katex-html", "aria-hidden": "true", children: [_jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mopen", children: "(" }), _jsx(_components.span, { className: "mord", children: "3" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2222em" } }), _jsx(_components.span, { className: "mbin", children: "+" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2222em" } })] }), _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mord", children: "4" }), _jsx(_components.span, { className: "mclose", children: ")" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2222em" } }), _jsx(_components.span, { className: "mbin", children: "×" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2222em" } })] }), _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mopen", children: "(" }), _jsx(_components.span, { className: "mord", children: "5" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2222em" } }), _jsx(_components.span, { className: "mbin", children: "−" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2222em" } })] }), _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mord", children: "2" }), _jsx(_components.span, { className: "mclose", children: ")" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2778em" } }), _jsx(_components.span, { className: "mrel", children: "=" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2778em" } })] }), _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "0.7278em", verticalAlign: "-0.0833em" } }), _jsx(_components.span, { className: "mord", children: "7" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2222em" } }), _jsx(_components.span, { className: "mbin", children: "×" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2222em" } })] }), _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "0.6444em" } }), _jsx(_components.span, { className: "mord", children: "3" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2778em" } }), _jsx(_components.span, { className: "mrel", children: "=" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2778em" } })] }), _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "0.6444em" } }), _jsx(_components.span, { className: "mord", children: "21" })] })] }) }), "."] }) })] }), _jsx(_components.pre, { children: _jsx(_components.code, { className: "language-mermaid", children: "flowchart TD\r\n A[\"* (Root)\"] --> B[\"+\"]\r\n A --> C[\"-\"]\r\n B --> D[\"3\"]\r\n B --> E[\"4\"]\r\n C --> F[\"5\"]\r\n C --> G[\"2\"]\r\n\r\n style A fill:#ff9999,stroke:#cc0000,stroke-width:2px\r\n style B fill:#99ccff,stroke:#0066cc,stroke-width:2px\r\n style C fill:#99ccff,stroke:#0066cc,stroke-width:2px\r\n style D fill:#99ff99,stroke:#009900,stroke-width:2px\r\n style E fill:#99ff99,stroke:#009900,stroke-width:2px\r\n style F fill:#99ff99,stroke:#009900,stroke-width:2px\r\n style G fill:#99ff99,stroke:#009900,stroke-width:2px\n" }) }), _jsxs(English, { children: [_jsx(_components.h3, { children: "🔍 Verifying with Traversals" }), _jsx(_components.p, { children: "Let us verify that the tree we built indeed gives the correct notations:" }), _jsxs(_components.ul, { children: ["\n", _jsxs(_components.li, { children: [_jsx(_components.strong, { children: "In-Order (Left → Root → Right):" }), " ", _jsx(_components.code, { children: "3 + 4 * 5 - 2" }), " — this is the ", _jsx(_components.strong, { children: "Infix" }), " form ✓"] }), "\n", _jsxs(_components.li, { children: [_jsx(_components.strong, { children: "Pre-Order (Root → Left → Right):" }), " ", _jsx(_components.code, { children: "* + 3 4 - 5 2" }), " — this is the ", _jsx(_components.strong, { children: "Prefix" }), " form ✓"] }), "\n", _jsxs(_components.li, { children: [_jsx(_components.strong, { children: "Post-Order (Left → Right → Root):" }), " ", _jsx(_components.code, { children: "3 4 + 5 2 - *" }), " — this is the ", _jsx(_components.strong, { children: "Postfix" }), " form ✓ (matches our input!)"] }), "\n"] }), _jsx(_components.p, { children: "This confirms that our Expression Tree construction is correct and demonstrates the power of traversal-notation mapping." })] }), _jsxs(Hinglish, { children: [_jsx(_components.h3, { children: "🔍 Traversals Se Verify Karna" }), _jsx(_components.p, { children: "Chaliye verify karte hain ki jo tree humne banaya hai woh sahi notations deta hai:" }), _jsxs(_components.ul, { children: ["\n", _jsxs(_components.li, { children: [_jsx(_components.strong, { children: "In-Order (Left → Root → Right):" }), " ", _jsx(_components.code, { children: "3 + 4 * 5 - 2" }), " — yeh ", _jsx(_components.strong, { children: "Infix" }), " form hai ✓"] }), "\n", _jsxs(_components.li, { children: [_jsx(_components.strong, { children: "Pre-Order (Root → Left → Right):" }), " ", _jsx(_components.code, { children: "* + 3 4 - 5 2" }), " — yeh ", _jsx(_components.strong, { children: "Prefix" }), " form hai ✓"] }), "\n", _jsxs(_components.li, { children: [_jsx(_components.strong, { children: "Post-Order (Left → Right → Root):" }), " ", _jsx(_components.code, { children: "3 4 + 5 2 - *" }), " — yeh ", _jsx(_components.strong, { children: "Postfix" }), " form hai ✓ (hamara input match karta hai!)"] }), "\n"] }), _jsx(_components.p, { children: "Yeh confirm karta hai ki hamara Expression Tree construction sahi hai aur traversal-notation mapping ki power dikhata hai." })] }), _jsxs(English, { children: [_jsx(_components.h3, { children: "⚡ Evaluating an Expression Tree" }), _jsxs(_components.p, { children: ["Evaluation of an Expression Tree is a ", _jsx(_components.strong, { children: "recursive process" }), ":"] }), _jsxs(_components.ol, { children: ["\n", _jsxs(_components.li, { children: ["If the node is a ", _jsx(_components.strong, { children: "leaf" }), " (operand), return its numeric value"] }), "\n", _jsxs(_components.li, { children: ["If the node is an ", _jsx(_components.strong, { children: "operator" }), ", recursively evaluate the left subtree, recursively evaluate the right subtree, and then apply the operator to both results"] }), "\n"] }), _jsxs(_components.p, { children: ["For our tree: evaluate left subtree of ", _jsx(_components.code, { children: "*" }), " → ", _jsx(_components.code, { children: "3 + 4 = 7" }), ", evaluate right subtree of ", _jsx(_components.code, { children: "*" }), " → ", _jsx(_components.code, { children: "5 - 2 = 3" }), ", then ", _jsx(_components.code, { children: "7 × 3 = 21" }), "."] }), _jsx(_components.p, { children: "Below is the complete C code for building and evaluating an Expression Tree from a postfix expression:" })] }), _jsxs(Hinglish, { children: [_jsx(_components.h3, { children: "⚡ Expression Tree Ka Evaluation" }), _jsxs(_components.p, { children: ["Expression Tree ka evaluation ek ", _jsx(_components.strong, { children: "recursive process" }), " hai:"] }), _jsxs(_components.ol, { children: ["\n", _jsxs(_components.li, { children: ["Agar node ", _jsx(_components.strong, { children: "leaf" }), " hai (operand), toh uska numeric value return karo"] }), "\n", _jsxs(_components.li, { children: ["Agar node ek ", _jsx(_components.strong, { children: "operator" }), " hai, toh recursively left subtree evaluate karo, recursively right subtree evaluate karo, phir dono results par operator apply karo"] }), "\n"] }), _jsxs(_components.p, { children: ["Hamare tree ke liye: ", _jsx(_components.code, { children: "*" }), " ka left subtree evaluate → ", _jsx(_components.code, { children: "3 + 4 = 7" }), ", ", _jsx(_components.code, { children: "*" }), " ka right subtree evaluate → ", _jsx(_components.code, { children: "5 - 2 = 3" }), ", phir ", _jsx(_components.code, { children: "7 × 3 = 21" }), "."] }), _jsx(_components.p, { children: "Neeche postfix expression se Expression Tree build aur evaluate karne ka complete C code hai:" })] }), _jsx(CodeBlock, { language: "c", children: `#include #include #include #include // Expression Tree Node struct Node { char data; struct Node *left, *right; }; // Create a new node struct Node* createNode(char ch) { struct Node* node = (struct Node*)malloc(sizeof(struct Node)); node->data = ch; node->left = node->right = NULL; return node; } // Build Expression Tree from Postfix struct Node* buildExprTree(char postfix[]) { struct Node* stack[100]; int top = -1; for (int i = 0; postfix[i] != '\\0'; i++) { struct Node* node = createNode(postfix[i]); if (isalnum(postfix[i])) { // Operand: push onto stack stack[++top] = node; } else { // Operator: pop two nodes as children node->right = stack[top--]; node->left = stack[top--]; stack[++top] = node; } } return stack[top]; // Root of tree } // Evaluate the Expression Tree int evaluate(struct Node* root) { if (root == NULL) return 0; // Leaf node: return numeric value if (root->left NULL && root->right NULL) return root->data - '0'; // Internal node: evaluate subtrees and apply operator int leftVal = evaluate(root->left); int rightVal = evaluate(root->right); switch (root->data) { case '+': return leftVal + rightVal; case '-': return leftVal - rightVal; case '*': return leftVal * rightVal; case '/': return leftVal / rightVal; } return 0; } int main() { char postfix[] = "34+52-*"; struct Node* root = buildExprTree(postfix); printf("Result: %d\\n", evaluate(root)); // Output: 21 return 0; }` }), _jsxs(English, { children: [_jsx(_components.h3, { children: "📦 Introduction to Heap" }), _jsxs(_components.p, { children: ["A ", _jsx(_components.strong, { children: "Heap" }), " is a complete binary tree that follows the heap property. Unlike general binary trees, heaps are typically ", _jsx(_components.strong, { children: "implemented using arrays" }), " rather than pointers. This is possible because a heap is always a ", _jsx(_components.strong, { children: "complete binary tree" }), " — meaning all levels are fully filled except possibly the last, which fills left to right. This completeness guarantees that there are no \"holes\" in the array, making the array representation both space-efficient and cache-friendly."] }), _jsx(_components.p, { children: "There are two types of heaps based on the heap property:" }), _jsxs(_components.ul, { children: ["\n", _jsxs(_components.li, { children: [_jsx(_components.strong, { children: "Max Heap:" }), " Every parent is ", _jsx(_components.strong, { children: "greater than or equal to" }), " its children → maximum element is always at the root"] }), "\n", _jsxs(_components.li, { children: [_jsx(_components.strong, { children: "Min Heap:" }), " Every parent is ", _jsx(_components.strong, { children: "less than or equal to" }), " its children → minimum element is always at the root"] }), "\n"] })] }), _jsxs(Hinglish, { children: [_jsx(_components.h3, { children: "📦 Heap Ka Introduction" }), _jsxs(_components.p, { children: [_jsx(_components.strong, { children: "Heap" }), " ek complete binary tree hai jo heap property follow karta hai. General binary trees ke unlike, heaps typically ", _jsx(_components.strong, { children: "arrays se implement" }), " kiye jaate hain pointers se nahi. Yeh isliye possible hai kyunki heap hamesha ek ", _jsx(_components.strong, { children: "complete binary tree" }), " hota hai — matlab sabhi levels fully filled hoti hain except possibly last, jo left to right se fill hoti hai. Yeh completeness guarantee karti hai ki array mein koi \"holes\" nahi hain, jisse array representation space-efficient aur cache-friendly dono hoti hai."] }), _jsx(_components.p, { children: "Heap property ke basis par do types ke heaps hain:" }), _jsxs(_components.ul, { children: ["\n", _jsxs(_components.li, { children: [_jsx(_components.strong, { children: "Max Heap:" }), " Har parent apne children se ", _jsx(_components.strong, { children: "bada ya barabar" }), " hota hai → maximum element hamesha root par hota hai"] }), "\n", _jsxs(_components.li, { children: [_jsx(_components.strong, { children: "Min Heap:" }), " Har parent apne children se ", _jsx(_components.strong, { children: "chhota ya barabar" }), " hota hai → minimum element hamesha root par hota hai"] }), "\n"] })] }), _jsx(Analogy, { children: _jsxs(_components.p, { children: [_jsx(_components.strong, { children: "Heap as a Corporate Hierarchy:" }), " Imagine a Max Heap as a company's organizational chart where the CEO (root) must always be the most senior person. Each VP (child of CEO) must be less senior than the CEO but more senior than their own managers (their children). The managers must be more senior than the interns reporting to them. This \"seniority rule\" at every level is the heap property. When someone new joins (insert), they start as an intern and may get promoted (bubble up) if they're more senior than their manager. When the CEO leaves (extract max), the most junior person from the bottom fills the spot and gets bubbled down to their appropriate level."] }) }), _jsx(ComparisonTable, { title: "Min Heap vs Max Heap", children: _jsxs(_components.table, { children: [_jsx(_components.thead, { children: _jsxs(_components.tr, { children: [_jsx(_components.th, { style: { textAlign: "left" }, children: "Feature" }), _jsx(_components.th, { style: { textAlign: "left" }, children: "Min Heap" }), _jsx(_components.th, { style: { textAlign: "left" }, children: "Max Heap" })] }) }), _jsxs(_components.tbody, { children: [_jsxs(_components.tr, { children: [_jsx(_components.td, { style: { textAlign: "left" }, children: _jsx(_components.strong, { children: "Heap Property" }) }), _jsx(_components.td, { style: { textAlign: "left" }, children: "Parent ≤ Children" }), _jsx(_components.td, { style: { textAlign: "left" }, children: "Parent ≥ Children" })] }), _jsxs(_components.tr, { children: [_jsx(_components.td, { style: { textAlign: "left" }, children: _jsx(_components.strong, { children: "Root Element" }) }), _jsx(_components.td, { style: { textAlign: "left" }, children: "Minimum value" }), _jsx(_components.td, { style: { textAlign: "left" }, children: "Maximum value" })] }), _jsxs(_components.tr, { children: [_jsx(_components.td, { style: { textAlign: "left" }, children: _jsx(_components.strong, { children: "Use Case" }) }), _jsx(_components.td, { style: { textAlign: "left" }, children: "Find minimum quickly, ascending sort" }), _jsx(_components.td, { style: { textAlign: "left" }, children: "Find maximum quickly, descending sort" })] }), _jsxs(_components.tr, { children: [_jsx(_components.td, { style: { textAlign: "left" }, children: _jsx(_components.strong, { children: "Priority Queue" }) }), _jsx(_components.td, { style: { textAlign: "left" }, children: "Highest priority = smallest value" }), _jsx(_components.td, { style: { textAlign: "left" }, children: "Highest priority = largest value" })] }), _jsxs(_components.tr, { children: [_jsx(_components.td, { style: { textAlign: "left" }, children: _jsx(_components.strong, { children: "Example Root" }) }), _jsxs(_components.td, { style: { textAlign: "left" }, children: ["Root of ", _jsx(_components.code, { children: "[10, 20, 15, 30, 25]" }), " is ", _jsx(_components.code, { children: "10" })] }), _jsxs(_components.td, { style: { textAlign: "left" }, children: ["Root of ", _jsx(_components.code, { children: "[50, 30, 40, 10, 20]" }), " is ", _jsx(_components.code, { children: "50" })] })] })] })] }) }), _jsxs(English, { children: [_jsx(_components.h3, { children: "🗂️ Array Representation of Heap" }), _jsxs(_components.p, { children: ["Since a heap is a complete binary tree, we can represent it using an ", _jsx(_components.strong, { children: "array with 1-based indexing" }), " (index 0 is left unused for cleaner math). The beauty of this representation is that the parent-child relationships can be calculated using simple formulas — no pointers needed!"] }), _jsxs(_components.p, { children: ["For a node at index ", _jsx(_components.span, { className: "katex", children: _jsx(_components.span, { className: "katex-html", "aria-hidden": "true", children: _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "0.6595em" } }), _jsx(_components.span, { className: "mord mathnormal", children: "i" })] }) }) }), ":"] }), _jsxs(_components.ul, { children: ["\n", _jsxs(_components.li, { children: [_jsx(_components.strong, { children: "Parent" }), " of node ", _jsx(_components.span, { className: "katex", children: _jsx(_components.span, { className: "katex-html", "aria-hidden": "true", children: _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "0.6595em" } }), _jsx(_components.span, { className: "mord mathnormal", children: "i" })] }) }) }), ": index ", _jsx(_components.span, { className: "katex", children: _jsx(_components.span, { className: "katex-html", "aria-hidden": "true", children: _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mopen", children: "⌊" }), _jsx(_components.span, { className: "mord mathnormal", children: "i" }), _jsx(_components.span, { className: "mord", children: "/2" }), _jsx(_components.span, { className: "mclose", children: "⌋" })] }) }) })] }), "\n", _jsxs(_components.li, { children: [_jsx(_components.strong, { children: "Left child" }), " of node ", _jsx(_components.span, { className: "katex", children: _jsx(_components.span, { className: "katex-html", "aria-hidden": "true", children: _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "0.6595em" } }), _jsx(_components.span, { className: "mord mathnormal", children: "i" })] }) }) }), ": index ", _jsx(_components.span, { className: "katex", children: _jsx(_components.span, { className: "katex-html", "aria-hidden": "true", children: _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "0.6595em" } }), _jsx(_components.span, { className: "mord", children: "2" }), _jsx(_components.span, { className: "mord mathnormal", children: "i" })] }) }) })] }), "\n", _jsxs(_components.li, { children: [_jsx(_components.strong, { children: "Right child" }), " of node ", _jsx(_components.span, { className: "katex", children: _jsx(_components.span, { className: "katex-html", "aria-hidden": "true", children: _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "0.6595em" } }), _jsx(_components.span, { className: "mord mathnormal", children: "i" })] }) }) }), ": index ", _jsx(_components.span, { className: "katex", children: _jsxs(_components.span, { className: "katex-html", "aria-hidden": "true", children: [_jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "0.7429em", verticalAlign: "-0.0833em" } }), _jsx(_components.span, { className: "mord", children: "2" }), _jsx(_components.span, { className: "mord mathnormal", children: "i" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2222em" } }), _jsx(_components.span, { className: "mbin", children: "+" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2222em" } })] }), _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "0.6444em" } }), _jsx(_components.span, { className: "mord", children: "1" })] })] }) })] }), "\n"] }), _jsxs(_components.p, { children: [_jsx(_components.strong, { children: "Example:" }), " Consider this Max Heap as a tree and its array representation:"] })] }), _jsxs(Hinglish, { children: [_jsx(_components.h3, { children: "🗂️ Heap Ka Array Representation" }), _jsxs(_components.p, { children: ["Kyunki heap ek complete binary tree hai, hum ise ", _jsx(_components.strong, { children: "1-based indexing wale array" }), " se represent kar sakte hain (index 0 mathematical simplicity ke liye chhoda jaata hai). Is representation ki beauty yeh hai ki parent-child relationships simple formulas se calculate ho sakte hain — pointers ki zaroorat nahi!"] }), _jsxs(_components.p, { children: ["Index ", _jsx(_components.span, { className: "katex", children: _jsx(_components.span, { className: "katex-html", "aria-hidden": "true", children: _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "0.6595em" } }), _jsx(_components.span, { className: "mord mathnormal", children: "i" })] }) }) }), " par ek node ke liye:"] }), _jsxs(_components.ul, { children: ["\n", _jsxs(_components.li, { children: ["Node ", _jsx(_components.span, { className: "katex", children: _jsx(_components.span, { className: "katex-html", "aria-hidden": "true", children: _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "0.6595em" } }), _jsx(_components.span, { className: "mord mathnormal", children: "i" })] }) }) }), " ka ", _jsx(_components.strong, { children: "Parent" }), ": index ", _jsx(_components.span, { className: "katex", children: _jsx(_components.span, { className: "katex-html", "aria-hidden": "true", children: _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mopen", children: "⌊" }), _jsx(_components.span, { className: "mord mathnormal", children: "i" }), _jsx(_components.span, { className: "mord", children: "/2" }), _jsx(_components.span, { className: "mclose", children: "⌋" })] }) }) })] }), "\n", _jsxs(_components.li, { children: ["Node ", _jsx(_components.span, { className: "katex", children: _jsx(_components.span, { className: "katex-html", "aria-hidden": "true", children: _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "0.6595em" } }), _jsx(_components.span, { className: "mord mathnormal", children: "i" })] }) }) }), " ka ", _jsx(_components.strong, { children: "Left child" }), ": index ", _jsx(_components.span, { className: "katex", children: _jsx(_components.span, { className: "katex-html", "aria-hidden": "true", children: _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "0.6595em" } }), _jsx(_components.span, { className: "mord", children: "2" }), _jsx(_components.span, { className: "mord mathnormal", children: "i" })] }) }) })] }), "\n", _jsxs(_components.li, { children: ["Node ", _jsx(_components.span, { className: "katex", children: _jsx(_components.span, { className: "katex-html", "aria-hidden": "true", children: _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "0.6595em" } }), _jsx(_components.span, { className: "mord mathnormal", children: "i" })] }) }) }), " ka ", _jsx(_components.strong, { children: "Right child" }), ": index ", _jsx(_components.span, { className: "katex", children: _jsxs(_components.span, { className: "katex-html", "aria-hidden": "true", children: [_jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "0.7429em", verticalAlign: "-0.0833em" } }), _jsx(_components.span, { className: "mord", children: "2" }), _jsx(_components.span, { className: "mord mathnormal", children: "i" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2222em" } }), _jsx(_components.span, { className: "mbin", children: "+" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2222em" } })] }), _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "0.6444em" } }), _jsx(_components.span, { className: "mord", children: "1" })] })] }) })] }), "\n"] }), _jsxs(_components.p, { children: [_jsx(_components.strong, { children: "Example:" }), " Is Max Heap ko tree aur uski array representation dekho:"] })] }), _jsx(_components.pre, { children: _jsx(_components.code, { className: "language-mermaid", children: "flowchart TD\r\n A[\"90 (i=1)\"] --> B[\"80 (i=2)\"]\r\n A --> C[\"70 (i=3)\"]\r\n B --> D[\"60 (i=4)\"]\r\n B --> E[\"50 (i=5)\"]\r\n C --> F[\"40 (i=6)\"]\r\n\r\n style A fill:#ff6666,stroke:#cc0000,stroke-width:3px\r\n style B fill:#ff9966,stroke:#cc6600,stroke-width:2px\r\n style C fill:#ff9966,stroke:#cc6600,stroke-width:2px\r\n style D fill:#ffcc66,stroke:#cc9900,stroke-width:2px\r\n style E fill:#ffcc66,stroke:#cc9900,stroke-width:2px\r\n style F fill:#ffcc66,stroke:#cc9900,stroke-width:2px\n" }) }), _jsxs(FormulaBox, { title: "Heap Index Formulas (1-Based Indexing)", children: [_jsx(_components.span, { className: "katex-display", children: _jsx(_components.span, { className: "katex", children: _jsxs(_components.span, { className: "katex-html", "aria-hidden": "true", children: [_jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "0.6944em" } }), _jsx(_components.span, { className: "mord text", children: _jsx(_components.span, { className: "mord", children: "Parent of node " }) }), _jsx(_components.span, { className: "mord mathnormal", children: "i" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2778em" } }), _jsx(_components.span, { className: "mrel", children: "=" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2778em" } })] }), _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mopen", children: "⌊" }), _jsx(_components.span, { className: "mord mathnormal", children: "i" }), _jsx(_components.span, { className: "mord", children: "/2" }), _jsx(_components.span, { className: "mclose", children: "⌋" })] })] }) }) }), _jsx(_components.span, { className: "katex-display", children: _jsx(_components.span, { className: "katex", children: _jsxs(_components.span, { className: "katex-html", "aria-hidden": "true", children: [_jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "0.6944em" } }), _jsx(_components.span, { className: "mord text", children: _jsx(_components.span, { className: "mord", children: "Left child of node " }) }), _jsx(_components.span, { className: "mord mathnormal", children: "i" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2778em" } }), _jsx(_components.span, { className: "mrel", children: "=" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2778em" } })] }), _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "0.6595em" } }), _jsx(_components.span, { className: "mord", children: "2" }), _jsx(_components.span, { className: "mord mathnormal", children: "i" })] })] }) }) }), _jsx(_components.span, { className: "katex-display", children: _jsx(_components.span, { className: "katex", children: _jsxs(_components.span, { className: "katex-html", "aria-hidden": "true", children: [_jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "0.8889em", verticalAlign: "-0.1944em" } }), _jsx(_components.span, { className: "mord text", children: _jsx(_components.span, { className: "mord", children: "Right child of node " }) }), _jsx(_components.span, { className: "mord mathnormal", children: "i" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2778em" } }), _jsx(_components.span, { className: "mrel", children: "=" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2778em" } })] }), _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "0.7429em", verticalAlign: "-0.0833em" } }), _jsx(_components.span, { className: "mord", children: "2" }), _jsx(_components.span, { className: "mord mathnormal", children: "i" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2222em" } }), _jsx(_components.span, { className: "mbin", children: "+" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2222em" } })] }), _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "0.6444em" } }), _jsx(_components.span, { className: "mord", children: "1" })] })] }) }) })] }), _jsxs(English, { children: [_jsxs(_components.p, { children: ["The corresponding array for the above heap: ", _jsx(_components.code, { children: "[_, 90, 80, 70, 60, 50, 40]" }), " (index 0 unused)."] }), _jsxs(_components.p, { children: ["Notice: For node ", _jsx(_components.code, { children: "80" }), " at index 2 → parent at index ", _jsx(_components.span, { className: "katex", children: _jsxs(_components.span, { className: "katex-html", "aria-hidden": "true", children: [_jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mopen", children: "⌊" }), _jsx(_components.span, { className: "mord", children: "2/2" }), _jsx(_components.span, { className: "mclose", children: "⌋" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2778em" } }), _jsx(_components.span, { className: "mrel", children: "=" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2778em" } })] }), _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "0.6444em" } }), _jsx(_components.span, { className: "mord", children: "1" })] })] }) }), " (value 90 ✓), left child at index ", _jsx(_components.span, { className: "katex", children: _jsxs(_components.span, { className: "katex-html", "aria-hidden": "true", children: [_jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "0.7278em", verticalAlign: "-0.0833em" } }), _jsx(_components.span, { className: "mord", children: "2" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2222em" } }), _jsx(_components.span, { className: "mbin", children: "×" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2222em" } })] }), _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "0.6444em" } }), _jsx(_components.span, { className: "mord", children: "2" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2778em" } }), _jsx(_components.span, { className: "mrel", children: "=" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2778em" } })] }), _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "0.6444em" } }), _jsx(_components.span, { className: "mord", children: "4" })] })] }) }), " (value 60 ✓), right child at index ", _jsx(_components.span, { className: "katex", children: _jsxs(_components.span, { className: "katex-html", "aria-hidden": "true", children: [_jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "0.7278em", verticalAlign: "-0.0833em" } }), _jsx(_components.span, { className: "mord", children: "2" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2222em" } }), _jsx(_components.span, { className: "mbin", children: "×" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2222em" } })] }), _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "0.7278em", verticalAlign: "-0.0833em" } }), _jsx(_components.span, { className: "mord", children: "2" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2222em" } }), _jsx(_components.span, { className: "mbin", children: "+" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2222em" } })] }), _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "0.6444em" } }), _jsx(_components.span, { className: "mord", children: "1" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2778em" } }), _jsx(_components.span, { className: "mrel", children: "=" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2778em" } })] }), _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "0.6444em" } }), _jsx(_components.span, { className: "mord", children: "5" })] })] }) }), " (value 50 ✓). The formulas work perfectly!"] })] }), _jsxs(Hinglish, { children: [_jsxs(_components.p, { children: ["Upar diye gaye heap ka corresponding array: ", _jsx(_components.code, { children: "[_, 90, 80, 70, 60, 50, 40]" }), " (index 0 unused)."] }), _jsxs(_components.p, { children: ["Dekho: Index 2 par node ", _jsx(_components.code, { children: "80" }), " → parent index ", _jsx(_components.span, { className: "katex", children: _jsxs(_components.span, { className: "katex-html", "aria-hidden": "true", children: [_jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mopen", children: "⌊" }), _jsx(_components.span, { className: "mord", children: "2/2" }), _jsx(_components.span, { className: "mclose", children: "⌋" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2778em" } }), _jsx(_components.span, { className: "mrel", children: "=" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2778em" } })] }), _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "0.6444em" } }), _jsx(_components.span, { className: "mord", children: "1" })] })] }) }), " par hai (value 90 ✓), left child index ", _jsx(_components.span, { className: "katex", children: _jsxs(_components.span, { className: "katex-html", "aria-hidden": "true", children: [_jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "0.7278em", verticalAlign: "-0.0833em" } }), _jsx(_components.span, { className: "mord", children: "2" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2222em" } }), _jsx(_components.span, { className: "mbin", children: "×" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2222em" } })] }), _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "0.6444em" } }), _jsx(_components.span, { className: "mord", children: "2" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2778em" } }), _jsx(_components.span, { className: "mrel", children: "=" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2778em" } })] }), _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "0.6444em" } }), _jsx(_components.span, { className: "mord", children: "4" })] })] }) }), " par hai (value 60 ✓), right child index ", _jsx(_components.span, { className: "katex", children: _jsxs(_components.span, { className: "katex-html", "aria-hidden": "true", children: [_jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "0.7278em", verticalAlign: "-0.0833em" } }), _jsx(_components.span, { className: "mord", children: "2" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2222em" } }), _jsx(_components.span, { className: "mbin", children: "×" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2222em" } })] }), _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "0.7278em", verticalAlign: "-0.0833em" } }), _jsx(_components.span, { className: "mord", children: "2" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2222em" } }), _jsx(_components.span, { className: "mbin", children: "+" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2222em" } })] }), _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "0.6444em" } }), _jsx(_components.span, { className: "mord", children: "1" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2778em" } }), _jsx(_components.span, { className: "mrel", children: "=" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2778em" } })] }), _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "0.6444em" } }), _jsx(_components.span, { className: "mord", children: "5" })] })] }) }), " par hai (value 50 ✓). Formulas perfectly kaam karte hain!"] })] }), _jsxs(English, { children: [_jsx(_components.h3, { children: "⬆️ Heap Insert Operation (Bubble Up / Percolate Up)" }), _jsx(_components.p, { children: "To insert a new element into a Max Heap:" }), _jsxs(_components.ol, { children: ["\n", _jsxs(_components.li, { children: ["Place the new element at the ", _jsx(_components.strong, { children: "next available position" }), " (end of the array) — this maintains the complete binary tree property"] }), "\n", _jsxs(_components.li, { children: [_jsx(_components.strong, { children: "Compare" }), " it with its parent. If the new element is ", _jsx(_components.strong, { children: "greater" }), " than its parent, ", _jsx(_components.strong, { children: "swap" }), " them"] }), "\n", _jsx(_components.li, { children: "Repeat step 2, moving up the tree, until the heap property is restored (or you reach the root)" }), "\n"] }), _jsxs(_components.p, { children: ["This upward movement is called ", _jsx(_components.strong, { children: "bubble up" }), " or ", _jsx(_components.strong, { children: "percolate up" }), " because the new (potentially large) element \"bubbles up\" to its correct position."] }), _jsxs(_components.p, { children: ["Let us trace the insertion of elements ", _jsx(_components.code, { children: "30, 50, 20, 40" }), " into an initially empty Max Heap:"] })] }), _jsxs(Hinglish, { children: [_jsx(_components.h3, { children: "⬆️ Heap Insert Operation (Bubble Up / Percolate Up)" }), _jsx(_components.p, { children: "Max Heap mein ek naya element insert karne ke liye:" }), _jsxs(_components.ol, { children: ["\n", _jsxs(_components.li, { children: ["Naye element ko ", _jsx(_components.strong, { children: "next available position" }), " par rakho (array ke end mein) — yeh complete binary tree property maintain karta hai"] }), "\n", _jsxs(_components.li, { children: ["Ise apne ", _jsx(_components.strong, { children: "parent se compare" }), " karo. Agar naya element parent se ", _jsx(_components.strong, { children: "bada" }), " hai, toh inhein ", _jsx(_components.strong, { children: "swap" }), " karo"] }), "\n", _jsx(_components.li, { children: "Step 2 repeat karo, tree mein upar ki taraf move karte hue, jab tak heap property restore na ho jaaye (ya root tak pahunch jao)" }), "\n"] }), _jsxs(_components.p, { children: ["Yeh upward movement ", _jsx(_components.strong, { children: "bubble up" }), " ya ", _jsx(_components.strong, { children: "percolate up" }), " kehlaati hai kyunki naya (potentially bada) element apni sahi position tak \"bubbles up\" karta hai."] }), _jsxs(_components.p, { children: ["Chaliye ", _jsx(_components.code, { children: "30, 50, 20, 40" }), " ko initially empty Max Heap mein insert karne ka trace dekhte hain:"] })] }), _jsxs(StepByStep, { title: "Max Heap Insert Trace: Insert 30, 50, 20, 40", children: [_jsx(Step, { title: "Insert 30", children: _jsxs(_components.p, { children: ["Place 30 at index 1 (root). Heap: ", _jsx(_components.code, { children: "[30]" }), ". No parent to compare — done! ✓"] }) }), _jsx(Step, { title: "Insert 50", children: _jsxs(_components.p, { children: ["Place 50 at index 2. Parent at index 1 is ", _jsx(_components.code, { children: "30" }), ". Since ", _jsx(_components.code, { children: "50 > 30" }), ", swap! Heap: ", _jsx(_components.code, { children: "[50, 30]" }), ". 50 is now at root — done! ✓"] }) }), _jsx(Step, { title: "Insert 20", children: _jsxs(_components.p, { children: ["Place 20 at index 3. Parent at index 1 is ", _jsx(_components.code, { children: "50" }), ". Since ", _jsx(_components.code, { children: "20 < 50" }), ", no swap needed. Heap: ", _jsx(_components.code, { children: "[50, 30, 20]" }), " ✓"] }) }), _jsx(Step, { title: "Insert 40", children: _jsxs(_components.p, { children: ["Place 40 at index 4. Parent at index 2 is ", _jsx(_components.code, { children: "30" }), ". Since ", _jsx(_components.code, { children: "40 > 30" }), ", swap! Now 40 is at index 2. Parent at index 1 is ", _jsx(_components.code, { children: "50" }), ". Since ", _jsx(_components.code, { children: "40 < 50" }), ", stop. Heap: ", _jsx(_components.code, { children: "[50, 40, 20, 30]" }), " ✓"] }) }), _jsx(Step, { title: "Final Max Heap", children: _jsxs(_components.p, { children: ["Array: ", _jsx(_components.code, { children: "[50, 40, 20, 30]" }), " — every parent is ≥ its children. Heap property satisfied!"] }) })] }), _jsxs(English, { children: [_jsx(_components.h3, { children: "⬇️ Heap Delete Operation (Extract Max) & Heapify" }), _jsxs(_components.p, { children: ["In a Max Heap, the ", _jsx(_components.strong, { children: "delete" }), " operation always removes the ", _jsx(_components.strong, { children: "maximum element" }), " (the root). The process is:"] }), _jsxs(_components.ol, { children: ["\n", _jsxs(_components.li, { children: [_jsx(_components.strong, { children: "Remove" }), " the root element (this is the maximum)"] }), "\n", _jsxs(_components.li, { children: [_jsx(_components.strong, { children: "Replace" }), " the root with the ", _jsx(_components.strong, { children: "last element" }), " in the array (to maintain complete binary tree structure)"] }), "\n", _jsxs(_components.li, { children: [_jsx(_components.strong, { children: "Heapify Down" }), " (also called bubble down or percolate down): Compare the new root with its children. If it is ", _jsx(_components.strong, { children: "smaller" }), " than the larger child, ", _jsx(_components.strong, { children: "swap" }), " with that child. Repeat downward until the heap property is restored."] }), "\n"] }), _jsxs(_components.p, { children: [_jsx(_components.strong, { children: "Heapify" }), " is the core operation. In a Max Heap, if a parent is smaller than its child, the heap property is violated, so we push the element downward to its correct position."] })] }), _jsxs(Hinglish, { children: [_jsx(_components.h3, { children: "⬇️ Heap Delete Operation (Extract Max) aur Heapify" }), _jsxs(_components.p, { children: ["Max Heap mein, ", _jsx(_components.strong, { children: "delete" }), " operation hamesha ", _jsx(_components.strong, { children: "maximum element" }), " (root) ko remove karta hai. Process hai:"] }), _jsxs(_components.ol, { children: ["\n", _jsxs(_components.li, { children: ["Root element ", _jsx(_components.strong, { children: "hatao" }), " (yeh maximum hai)"] }), "\n", _jsxs(_components.li, { children: ["Root ko array ke ", _jsx(_components.strong, { children: "last element" }), " se ", _jsx(_components.strong, { children: "replace" }), " karo (complete binary tree structure maintain karne ke liye)"] }), "\n", _jsxs(_components.li, { children: [_jsx(_components.strong, { children: "Heapify Down" }), " (bubble down ya percolate down bhi kehte hain): Naye root ko uske children se compare karo. Agar woh ", _jsx(_components.strong, { children: "bade child se chhota" }), " hai, toh uss child ke saath ", _jsx(_components.strong, { children: "swap" }), " karo. Tab tak neeche ki taraf repeat karo jab tak heap property restore na ho jaaye."] }), "\n"] }), _jsxs(_components.p, { children: [_jsx(_components.strong, { children: "Heapify" }), " core operation hai. Max Heap mein, agar parent apne child se chhota hai, toh heap property violate hoti hai, toh hum element ko uski sahi position tak neeche push karte hain."] })] }), _jsxs(StepByStep, { title: "Max Heap Delete Trace: Extract Max from [90, 80, 70, 60, 50]", children: [_jsx(Step, { title: "Initial Heap", children: _jsxs(_components.p, { children: ["Array: ", _jsx(_components.code, { children: "[90, 80, 70, 60, 50]" }), ". Root (max) = 90. We want to remove 90."] }) }), _jsx(Step, { title: "Remove Root, Replace with Last", children: _jsxs(_components.p, { children: ["Remove 90. Replace with last element 50. Array: ", _jsx(_components.code, { children: "[50, 80, 70, 60]" }), " (n = 4 now)."] }) }), _jsx(Step, { title: "Heapify Down — Level 1", children: _jsxs(_components.p, { children: ["Root is 50. Children: left = 80, right = 70. Larger child = 80. Since ", _jsx(_components.code, { children: "50 < 80" }), ", swap! Array: ", _jsx(_components.code, { children: "[80, 50, 70, 60]" }), "."] }) }), _jsx(Step, { title: "Heapify Down — Level 2", children: _jsxs(_components.p, { children: ["50 is now at index 2. Children: left = 60 (index 4). Since ", _jsx(_components.code, { children: "50 < 60" }), ", swap! Array: ", _jsx(_components.code, { children: "[80, 60, 70, 50]" }), "."] }) }), _jsx(Step, { title: "Heapify Complete", children: _jsxs(_components.p, { children: ["50 is now at index 4, which is a leaf. No more children. Done! Final heap: ", _jsx(_components.code, { children: "[80, 60, 70, 50]" }), ". Root is 80 (new maximum) ✓"] }) })] }), _jsx(English, { children: _jsx(_components.p, { children: "Below is the complete C code for all heap operations — insert (bubble up), heapify (bubble down), extract max, and build heap:" }) }), _jsx(Hinglish, { children: _jsx(_components.p, { children: "Neeche saare heap operations ka complete C code hai — insert (bubble up), heapify (bubble down), extract max, aur build heap:" }) }), _jsx(CodeBlock, { language: "c", children: `#include // Swap two elements void swap(int *a, int *b) { int temp = *a; *a = *b; *b = temp; } // ---- MAX HEAP OPERATIONS ---- // Heapify Down: restore max heap property from index i downward void maxHeapify(int heap[], int n, int i) { int largest = i; // Assume current node is largest int left = 2 * i; // Left child index int right = 2 * i + 1; // Right child index if (left <= n && heap[left] > heap[largest]) largest = left; if (right <= n && heap[right] > heap[largest]) largest = right; if (largest != i) { swap(&heap[i], &heap[largest]); maxHeapify(heap, n, largest); // Recurse downward } } // Insert element into Max Heap (Bubble Up) void insertMaxHeap(int heap[], int *n, int val) { (*n)++; heap[*n] = val; int i = *n; // Bubble up: compare with parent and swap if larger while (i > 1 && heap[i / 2] < heap[i]) { swap(&heap[i / 2], &heap[i]); i = i / 2; } } // Extract maximum element from Max Heap int extractMax(int heap[], int *n) { int max = heap[1]; // Root is the maximum heap[1] = heap[*n]; // Replace root with last element (*n)--; maxHeapify(heap, *n, 1); // Heapify from root return max; } // Build Max Heap from an unsorted array void buildMaxHeap(int heap[], int n) { for (int i = n / 2; i >= 1; i--) { maxHeapify(heap, n, i); } } int main() { int heap[100] = {0}; int n = 0; // Insert elements insertMaxHeap(heap, &n, 30); insertMaxHeap(heap, &n, 50); insertMaxHeap(heap, &n, 20); insertMaxHeap(heap, &n, 40); insertMaxHeap(heap, &n, 10); printf("Max Heap: "); for (int i = 1; i <= n; i++) printf("%d ", heap[i]); // Output: 50 40 20 30 10 printf("\\n"); // Extract max printf("Extracted: %d\\n", extractMax(heap, &n)); // 50 printf("After extraction: "); for (int i = 1; i <= n; i++) printf("%d ", heap[i]); // Output: 40 30 20 10 printf("\\n"); return 0; }` }), _jsxs(English, { children: [_jsx(_components.h3, { children: "🔨 Build Heap Operation" }), _jsxs(_components.p, { children: ["Sometimes we have an unsorted array and want to convert it into a heap. Instead of inserting elements one by one (which takes ", _jsx(_components.span, { className: "katex", children: _jsx(_components.span, { className: "katex-html", "aria-hidden": "true", children: _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.0278em" }, children: "O" }), _jsx(_components.span, { className: "mopen", children: "(" }), _jsx(_components.span, { className: "mord mathnormal", children: "n" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.1667em" } }), _jsxs(_components.span, { className: "mop", children: ["lo", _jsx(_components.span, { style: { marginRight: "0.0139em" }, children: "g" })] }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.1667em" } }), _jsx(_components.span, { className: "mord mathnormal", children: "n" }), _jsx(_components.span, { className: "mclose", children: ")" })] }) }) }), "), we can use the ", _jsx(_components.strong, { children: "Build Heap" }), " algorithm which runs in ", _jsx(_components.strong, { children: _jsx(_components.span, { className: "katex", children: _jsx(_components.span, { className: "katex-html", "aria-hidden": "true", children: _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.0278em" }, children: "O" }), _jsx(_components.span, { className: "mopen", children: "(" }), _jsx(_components.span, { className: "mord mathnormal", children: "n" }), _jsx(_components.span, { className: "mclose", children: ")" })] }) }) }) }), " time. The idea is simple: start from the last non-leaf node and call ", _jsx(_components.code, { children: "heapify" }), " on each node, moving upward to the root. Since leaf nodes already satisfy the heap property (they have no children), we only need to process nodes from index ", _jsx(_components.span, { className: "katex", children: _jsx(_components.span, { className: "katex-html", "aria-hidden": "true", children: _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mopen", children: "⌊" }), _jsx(_components.span, { className: "mord mathnormal", children: "n" }), _jsx(_components.span, { className: "mord", children: "/2" }), _jsx(_components.span, { className: "mclose", children: "⌋" })] }) }) }), " down to 1."] }), _jsx(_components.p, { children: _jsx(_components.strong, { children: "Time Complexity Summary:" }) }), _jsxs(_components.ul, { children: ["\n", _jsxs(_components.li, { children: [_jsx(_components.strong, { children: "Insert (Bubble Up):" }), " ", _jsx(_components.span, { className: "katex", children: _jsx(_components.span, { className: "katex-html", "aria-hidden": "true", children: _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.0278em" }, children: "O" }), _jsx(_components.span, { className: "mopen", children: "(" }), _jsxs(_components.span, { className: "mop", children: ["lo", _jsx(_components.span, { style: { marginRight: "0.0139em" }, children: "g" })] }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.1667em" } }), _jsx(_components.span, { className: "mord mathnormal", children: "n" }), _jsx(_components.span, { className: "mclose", children: ")" })] }) }) }), " — at most the height of the tree"] }), "\n", _jsxs(_components.li, { children: [_jsx(_components.strong, { children: "Extract Max/Min (Heapify Down):" }), " ", _jsx(_components.span, { className: "katex", children: _jsx(_components.span, { className: "katex-html", "aria-hidden": "true", children: _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.0278em" }, children: "O" }), _jsx(_components.span, { className: "mopen", children: "(" }), _jsxs(_components.span, { className: "mop", children: ["lo", _jsx(_components.span, { style: { marginRight: "0.0139em" }, children: "g" })] }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.1667em" } }), _jsx(_components.span, { className: "mord mathnormal", children: "n" }), _jsx(_components.span, { className: "mclose", children: ")" })] }) }) }), " — at most the height of the tree"] }), "\n", _jsxs(_components.li, { children: [_jsx(_components.strong, { children: "Heapify:" }), " ", _jsx(_components.span, { className: "katex", children: _jsx(_components.span, { className: "katex-html", "aria-hidden": "true", children: _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.0278em" }, children: "O" }), _jsx(_components.span, { className: "mopen", children: "(" }), _jsxs(_components.span, { className: "mop", children: ["lo", _jsx(_components.span, { style: { marginRight: "0.0139em" }, children: "g" })] }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.1667em" } }), _jsx(_components.span, { className: "mord mathnormal", children: "n" }), _jsx(_components.span, { className: "mclose", children: ")" })] }) }) }), " in the worst case"] }), "\n", _jsxs(_components.li, { children: [_jsx(_components.strong, { children: "Build Heap:" }), " ", _jsx(_components.span, { className: "katex", children: _jsx(_components.span, { className: "katex-html", "aria-hidden": "true", children: _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.0278em" }, children: "O" }), _jsx(_components.span, { className: "mopen", children: "(" }), _jsx(_components.span, { className: "mord mathnormal", children: "n" }), _jsx(_components.span, { className: "mclose", children: ")" })] }) }) }), " — this is NOT ", _jsx(_components.span, { className: "katex", children: _jsx(_components.span, { className: "katex-html", "aria-hidden": "true", children: _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.0278em" }, children: "O" }), _jsx(_components.span, { className: "mopen", children: "(" }), _jsx(_components.span, { className: "mord mathnormal", children: "n" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.1667em" } }), _jsxs(_components.span, { className: "mop", children: ["lo", _jsx(_components.span, { style: { marginRight: "0.0139em" }, children: "g" })] }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.1667em" } }), _jsx(_components.span, { className: "mord mathnormal", children: "n" }), _jsx(_components.span, { className: "mclose", children: ")" })] }) }) }), "; the mathematical proof shows it is linear"] }), "\n", _jsxs(_components.li, { children: [_jsx(_components.strong, { children: "Heap Sort:" }), " ", _jsx(_components.span, { className: "katex", children: _jsx(_components.span, { className: "katex-html", "aria-hidden": "true", children: _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.0278em" }, children: "O" }), _jsx(_components.span, { className: "mopen", children: "(" }), _jsx(_components.span, { className: "mord mathnormal", children: "n" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.1667em" } }), _jsxs(_components.span, { className: "mop", children: ["lo", _jsx(_components.span, { style: { marginRight: "0.0139em" }, children: "g" })] }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.1667em" } }), _jsx(_components.span, { className: "mord mathnormal", children: "n" }), _jsx(_components.span, { className: "mclose", children: ")" })] }) }) }), " — build heap + extract n times"] }), "\n"] })] }), _jsxs(Hinglish, { children: [_jsx(_components.h3, { children: "🔨 Build Heap Operation" }), _jsxs(_components.p, { children: ["Kabhi kabhi humare paas ek unsorted array hota hai aur use heap mein convert karna hota hai. Elements ko ek ek karke insert karne ke bajaye (", _jsx(_components.span, { className: "katex", children: _jsx(_components.span, { className: "katex-html", "aria-hidden": "true", children: _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.0278em" }, children: "O" }), _jsx(_components.span, { className: "mopen", children: "(" }), _jsx(_components.span, { className: "mord mathnormal", children: "n" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.1667em" } }), _jsxs(_components.span, { className: "mop", children: ["lo", _jsx(_components.span, { style: { marginRight: "0.0139em" }, children: "g" })] }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.1667em" } }), _jsx(_components.span, { className: "mord mathnormal", children: "n" }), _jsx(_components.span, { className: "mclose", children: ")" })] }) }) }), " lagta hai), hum ", _jsx(_components.strong, { children: "Build Heap" }), " algorithm use kar sakte hain jo ", _jsx(_components.strong, { children: _jsx(_components.span, { className: "katex", children: _jsx(_components.span, { className: "katex-html", "aria-hidden": "true", children: _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.0278em" }, children: "O" }), _jsx(_components.span, { className: "mopen", children: "(" }), _jsx(_components.span, { className: "mord mathnormal", children: "n" }), _jsx(_components.span, { className: "mclose", children: ")" })] }) }) }) }), " time mein chalta hai. Idea simple hai: last non-leaf node se shuru karo aur har node par ", _jsx(_components.code, { children: "heapify" }), " call karo, root ki taraf upar ki taraf move karte hue. Kyunki leaf nodes already heap property satisfy karte hain (unke koi children nahi hain), humein sirf index ", _jsx(_components.span, { className: "katex", children: _jsx(_components.span, { className: "katex-html", "aria-hidden": "true", children: _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mopen", children: "⌊" }), _jsx(_components.span, { className: "mord mathnormal", children: "n" }), _jsx(_components.span, { className: "mord", children: "/2" }), _jsx(_components.span, { className: "mclose", children: "⌋" })] }) }) }), " se 1 tak nodes process karne hain."] }), _jsx(_components.p, { children: _jsx(_components.strong, { children: "Time Complexity Summary:" }) }), _jsxs(_components.ul, { children: ["\n", _jsxs(_components.li, { children: [_jsx(_components.strong, { children: "Insert (Bubble Up):" }), " ", _jsx(_components.span, { className: "katex", children: _jsx(_components.span, { className: "katex-html", "aria-hidden": "true", children: _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.0278em" }, children: "O" }), _jsx(_components.span, { className: "mopen", children: "(" }), _jsxs(_components.span, { className: "mop", children: ["lo", _jsx(_components.span, { style: { marginRight: "0.0139em" }, children: "g" })] }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.1667em" } }), _jsx(_components.span, { className: "mord mathnormal", children: "n" }), _jsx(_components.span, { className: "mclose", children: ")" })] }) }) }), " — tree ki height se zyada nahi"] }), "\n", _jsxs(_components.li, { children: [_jsx(_components.strong, { children: "Extract Max/Min (Heapify Down):" }), " ", _jsx(_components.span, { className: "katex", children: _jsx(_components.span, { className: "katex-html", "aria-hidden": "true", children: _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.0278em" }, children: "O" }), _jsx(_components.span, { className: "mopen", children: "(" }), _jsxs(_components.span, { className: "mop", children: ["lo", _jsx(_components.span, { style: { marginRight: "0.0139em" }, children: "g" })] }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.1667em" } }), _jsx(_components.span, { className: "mord mathnormal", children: "n" }), _jsx(_components.span, { className: "mclose", children: ")" })] }) }) }), " — tree ki height se zyada nahi"] }), "\n", _jsxs(_components.li, { children: [_jsx(_components.strong, { children: "Heapify:" }), " worst case mein ", _jsx(_components.span, { className: "katex", children: _jsx(_components.span, { className: "katex-html", "aria-hidden": "true", children: _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.0278em" }, children: "O" }), _jsx(_components.span, { className: "mopen", children: "(" }), _jsxs(_components.span, { className: "mop", children: ["lo", _jsx(_components.span, { style: { marginRight: "0.0139em" }, children: "g" })] }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.1667em" } }), _jsx(_components.span, { className: "mord mathnormal", children: "n" }), _jsx(_components.span, { className: "mclose", children: ")" })] }) }) })] }), "\n", _jsxs(_components.li, { children: [_jsx(_components.strong, { children: "Build Heap:" }), " ", _jsx(_components.span, { className: "katex", children: _jsx(_components.span, { className: "katex-html", "aria-hidden": "true", children: _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.0278em" }, children: "O" }), _jsx(_components.span, { className: "mopen", children: "(" }), _jsx(_components.span, { className: "mord mathnormal", children: "n" }), _jsx(_components.span, { className: "mclose", children: ")" })] }) }) }), " — yeh ", _jsx(_components.span, { className: "katex", children: _jsx(_components.span, { className: "katex-html", "aria-hidden": "true", children: _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.0278em" }, children: "O" }), _jsx(_components.span, { className: "mopen", children: "(" }), _jsx(_components.span, { className: "mord mathnormal", children: "n" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.1667em" } }), _jsxs(_components.span, { className: "mop", children: ["lo", _jsx(_components.span, { style: { marginRight: "0.0139em" }, children: "g" })] }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.1667em" } }), _jsx(_components.span, { className: "mord mathnormal", children: "n" }), _jsx(_components.span, { className: "mclose", children: ")" })] }) }) }), " nahi hai; mathematical proof dikhata hai ki yeh linear hai"] }), "\n", _jsxs(_components.li, { children: [_jsx(_components.strong, { children: "Heap Sort:" }), " ", _jsx(_components.span, { className: "katex", children: _jsx(_components.span, { className: "katex-html", "aria-hidden": "true", children: _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.0278em" }, children: "O" }), _jsx(_components.span, { className: "mopen", children: "(" }), _jsx(_components.span, { className: "mord mathnormal", children: "n" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.1667em" } }), _jsxs(_components.span, { className: "mop", children: ["lo", _jsx(_components.span, { style: { marginRight: "0.0139em" }, children: "g" })] }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.1667em" } }), _jsx(_components.span, { className: "mord mathnormal", children: "n" }), _jsx(_components.span, { className: "mclose", children: ")" })] }) }) }), " — build heap + n baar extract"] }), "\n"] })] }), _jsxs(Applications, { title: "Expression Tree and Heap Applications", children: [_jsx(_components.p, { children: _jsx(_components.strong, { children: "Expression Tree Applications:" }) }), _jsxs(_components.ul, { children: ["\n", _jsxs(_components.li, { children: [_jsx(_components.strong, { children: "Compilers and Interpreters:" }), " Used to parse and optimize mathematical expressions during code compilation"] }), "\n", _jsxs(_components.li, { children: [_jsx(_components.strong, { children: "Calculators:" }), " Scientific calculators use expression trees to evaluate complex nested expressions"] }), "\n", _jsxs(_components.li, { children: [_jsx(_components.strong, { children: "Database Query Optimization:" }), " Query planners use tree representations to find optimal execution plans"] }), "\n", _jsxs(_components.li, { children: [_jsx(_components.strong, { children: "Symbolic Mathematics:" }), " Computer algebra systems use expression trees for algebraic simplification"] }), "\n"] }), _jsx(_components.p, { children: _jsx(_components.strong, { children: "Heap Applications:" }) }), _jsxs(_components.ul, { children: ["\n", _jsxs(_components.li, { children: [_jsx(_components.strong, { children: "Priority Queues:" }), " Heaps are the most efficient implementation of priority queues — used in operating systems for process scheduling, in networking for packet scheduling, and in many algorithms"] }), "\n", _jsxs(_components.li, { children: [_jsx(_components.strong, { children: "Heap Sort:" }), " An efficient ", _jsx(_components.span, { className: "katex", children: _jsx(_components.span, { className: "katex-html", "aria-hidden": "true", children: _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.0278em" }, children: "O" }), _jsx(_components.span, { className: "mopen", children: "(" }), _jsx(_components.span, { className: "mord mathnormal", children: "n" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.1667em" } }), _jsxs(_components.span, { className: "mop", children: ["lo", _jsx(_components.span, { style: { marginRight: "0.0139em" }, children: "g" })] }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.1667em" } }), _jsx(_components.span, { className: "mord mathnormal", children: "n" }), _jsx(_components.span, { className: "mclose", children: ")" })] }) }) }), " comparison-based sorting algorithm"] }), "\n", _jsxs(_components.li, { children: [_jsx(_components.strong, { children: "Finding Kth Largest/Smallest Element:" }), " Using a Min Heap of size K"] }), "\n", _jsxs(_components.li, { children: [_jsx(_components.strong, { children: "Dijkstra's Shortest Path Algorithm:" }), " Uses a priority queue (heap) to efficiently find the shortest path"] }), "\n", _jsxs(_components.li, { children: [_jsx(_components.strong, { children: "Median Maintenance:" }), " Using two heaps (a Max Heap for the lower half and a Min Heap for the upper half)"] }), "\n"] })] }), _jsx(KeyPoints, { children: _jsxs(_components.ul, { children: ["\n", _jsxs(_components.li, { children: ["An ", _jsx(_components.strong, { children: "Expression Tree" }), " is a binary tree where leaf nodes are operands and internal nodes are operators — it represents mathematical expressions naturally"] }), "\n", _jsxs(_components.li, { children: [_jsx(_components.strong, { children: "In-Order traversal" }), " gives Infix, ", _jsx(_components.strong, { children: "Pre-Order" }), " gives Prefix, ", _jsx(_components.strong, { children: "Post-Order" }), " gives Postfix notation"] }), "\n", _jsxs(_components.li, { children: ["Expression Trees are built from ", _jsx(_components.strong, { children: "postfix expressions" }), " using a ", _jsx(_components.strong, { children: "stack-based algorithm" }), " — operands are pushed, operators pop two nodes as children"] }), "\n", _jsxs(_components.li, { children: ["A ", _jsx(_components.strong, { children: "Heap" }), " is a complete binary tree with the heap property — implemented using arrays, not pointers"] }), "\n", _jsxs(_components.li, { children: [_jsx(_components.strong, { children: "Max Heap:" }), " Parent ≥ Children (root is maximum); ", _jsx(_components.strong, { children: "Min Heap:" }), " Parent ≤ Children (root is minimum)"] }), "\n", _jsxs(_components.li, { children: ["Heap array formulas (1-based): parent = ", _jsx(_components.span, { className: "katex", children: _jsx(_components.span, { className: "katex-html", "aria-hidden": "true", children: _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mopen", children: "⌊" }), _jsx(_components.span, { className: "mord mathnormal", children: "i" }), _jsx(_components.span, { className: "mord", children: "/2" }), _jsx(_components.span, { className: "mclose", children: "⌋" })] }) }) }), ", left child = ", _jsx(_components.span, { className: "katex", children: _jsx(_components.span, { className: "katex-html", "aria-hidden": "true", children: _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "0.6595em" } }), _jsx(_components.span, { className: "mord", children: "2" }), _jsx(_components.span, { className: "mord mathnormal", children: "i" })] }) }) }), ", right child = ", _jsx(_components.span, { className: "katex", children: _jsxs(_components.span, { className: "katex-html", "aria-hidden": "true", children: [_jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "0.7429em", verticalAlign: "-0.0833em" } }), _jsx(_components.span, { className: "mord", children: "2" }), _jsx(_components.span, { className: "mord mathnormal", children: "i" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2222em" } }), _jsx(_components.span, { className: "mbin", children: "+" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2222em" } })] }), _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "0.6444em" } }), _jsx(_components.span, { className: "mord", children: "1" })] })] }) })] }), "\n", _jsxs(_components.li, { children: [_jsx(_components.strong, { children: "Insert" }), " uses ", _jsx(_components.strong, { children: "Bubble Up" }), " (compare with parent, swap if needed): ", _jsx(_components.span, { className: "katex", children: _jsx(_components.span, { className: "katex-html", "aria-hidden": "true", children: _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.0278em" }, children: "O" }), _jsx(_components.span, { className: "mopen", children: "(" }), _jsxs(_components.span, { className: "mop", children: ["lo", _jsx(_components.span, { style: { marginRight: "0.0139em" }, children: "g" })] }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.1667em" } }), _jsx(_components.span, { className: "mord mathnormal", children: "n" }), _jsx(_components.span, { className: "mclose", children: ")" })] }) }) })] }), "\n", _jsxs(_components.li, { children: [_jsx(_components.strong, { children: "Extract Max/Min" }), " uses ", _jsx(_components.strong, { children: "Heapify Down" }), " (compare with children, swap with larger/smaller child): ", _jsx(_components.span, { className: "katex", children: _jsx(_components.span, { className: "katex-html", "aria-hidden": "true", children: _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.0278em" }, children: "O" }), _jsx(_components.span, { className: "mopen", children: "(" }), _jsxs(_components.span, { className: "mop", children: ["lo", _jsx(_components.span, { style: { marginRight: "0.0139em" }, children: "g" })] }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.1667em" } }), _jsx(_components.span, { className: "mord mathnormal", children: "n" }), _jsx(_components.span, { className: "mclose", children: ")" })] }) }) })] }), "\n", _jsxs(_components.li, { children: [_jsx(_components.strong, { children: "Build Heap" }), " from an unsorted array takes ", _jsx(_components.strong, { children: _jsx(_components.span, { className: "katex", children: _jsx(_components.span, { className: "katex-html", "aria-hidden": "true", children: _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.0278em" }, children: "O" }), _jsx(_components.span, { className: "mopen", children: "(" }), _jsx(_components.span, { className: "mord mathnormal", children: "n" }), _jsx(_components.span, { className: "mclose", children: ")" })] }) }) }) }), " time — not ", _jsx(_components.span, { className: "katex", children: _jsx(_components.span, { className: "katex-html", "aria-hidden": "true", children: _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.0278em" }, children: "O" }), _jsx(_components.span, { className: "mopen", children: "(" }), _jsx(_components.span, { className: "mord mathnormal", children: "n" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.1667em" } }), _jsxs(_components.span, { className: "mop", children: ["lo", _jsx(_components.span, { style: { marginRight: "0.0139em" }, children: "g" })] }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.1667em" } }), _jsx(_components.span, { className: "mord mathnormal", children: "n" }), _jsx(_components.span, { className: "mclose", children: ")" })] }) }) })] }), "\n", _jsxs(_components.li, { children: ["Heaps are the backbone of ", _jsx(_components.strong, { children: "Priority Queues" }), ", ", _jsx(_components.strong, { children: "Heap Sort" }), ", and many graph algorithms"] }), "\n"] }) }), _jsx(Remember, { title: "Common Exam Mistakes", children: _jsxs(_components.ul, { children: ["\n", _jsxs(_components.li, { children: [_jsx(_components.strong, { children: "Heap is NOT a BST!" }), " In a BST, left < root < right. In a heap, only the parent-child relationship matters — there is no ordering between siblings"] }), "\n", _jsxs(_components.li, { children: [_jsx(_components.strong, { children: "Heapify direction matters:" }), " For insertion, bubble UP (towards root). For deletion, bubble DOWN (towards leaves). Confusing these is a very common mistake"] }), "\n", _jsxs(_components.li, { children: [_jsx(_components.strong, { children: "Expression Tree building:" }), " Remember that the first popped node from the stack becomes the RIGHT child and the second becomes the LEFT child — not the other way around!"] }), "\n", _jsxs(_components.li, { children: [_jsx(_components.strong, { children: "Array indexing:" }), " Most heap implementations use 1-based indexing for cleaner formulas. If you use 0-based, the formulas change to: parent = ", _jsx(_components.span, { className: "katex", children: _jsxs(_components.span, { className: "katex-html", "aria-hidden": "true", children: [_jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mopen", children: "⌊(" }), _jsx(_components.span, { className: "mord mathnormal", children: "i" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2222em" } }), _jsx(_components.span, { className: "mbin", children: "−" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2222em" } })] }), _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mord", children: "1" }), _jsx(_components.span, { className: "mclose", children: ")" }), _jsx(_components.span, { className: "mord", children: "/2" }), _jsx(_components.span, { className: "mclose", children: "⌋" })] })] }) }), ", left = ", _jsx(_components.span, { className: "katex", children: _jsxs(_components.span, { className: "katex-html", "aria-hidden": "true", children: [_jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "0.7429em", verticalAlign: "-0.0833em" } }), _jsx(_components.span, { className: "mord", children: "2" }), _jsx(_components.span, { className: "mord mathnormal", children: "i" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2222em" } }), _jsx(_components.span, { className: "mbin", children: "+" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2222em" } })] }), _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "0.6444em" } }), _jsx(_components.span, { className: "mord", children: "1" })] })] }) }), ", right = ", _jsx(_components.span, { className: "katex", children: _jsxs(_components.span, { className: "katex-html", "aria-hidden": "true", children: [_jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "0.7429em", verticalAlign: "-0.0833em" } }), _jsx(_components.span, { className: "mord", children: "2" }), _jsx(_components.span, { className: "mord mathnormal", children: "i" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2222em" } }), _jsx(_components.span, { className: "mbin", children: "+" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2222em" } })] }), _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "0.6444em" } }), _jsx(_components.span, { className: "mord", children: "2" })] })] }) })] }), "\n", _jsxs(_components.li, { children: [_jsxs(_components.strong, { children: ["Build Heap is ", _jsx(_components.span, { className: "katex", children: _jsx(_components.span, { className: "katex-html", "aria-hidden": "true", children: _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.0278em" }, children: "O" }), _jsx(_components.span, { className: "mopen", children: "(" }), _jsx(_components.span, { className: "mord mathnormal", children: "n" }), _jsx(_components.span, { className: "mclose", children: ")" })] }) }) }), ":"] }), " Do NOT write ", _jsx(_components.span, { className: "katex", children: _jsx(_components.span, { className: "katex-html", "aria-hidden": "true", children: _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.0278em" }, children: "O" }), _jsx(_components.span, { className: "mopen", children: "(" }), _jsx(_components.span, { className: "mord mathnormal", children: "n" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.1667em" } }), _jsxs(_components.span, { className: "mop", children: ["lo", _jsx(_components.span, { style: { marginRight: "0.0139em" }, children: "g" })] }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.1667em" } }), _jsx(_components.span, { className: "mord mathnormal", children: "n" }), _jsx(_components.span, { className: "mclose", children: ")" })] }) }) }), " for build heap in exams — this is a common mistake that costs marks!"] }), "\n"] }) })] })] }), "\n", _jsx(Practical, { children: _jsxs(ImportantQA, { children: [_jsxs(QAQuestion, { marks: 2, children: [_jsx(Prompt, { children: "Define an Expression Tree and give one example expression tree for 'A + B * C'." }), _jsxs(Answer, { children: [_jsx(_components.h3, { children: "📝 Definition" }), _jsxs(_components.p, { children: ["An ", _jsx(_components.strong, { children: "Expression Tree" }), " is a special type of binary tree used to represent mathematical expressions. In this tree:"] }), _jsxs(_components.ul, { children: ["\n", _jsxs(_components.li, { children: ["Every ", _jsx(_components.strong, { children: "leaf node" }), " is an ", _jsx(_components.strong, { children: "operand" }), " (like numbers or variables)."] }), "\n", _jsxs(_components.li, { children: ["Every ", _jsx(_components.strong, { children: "internal node" }), " is an ", _jsx(_components.strong, { children: "operator" }), " (like ", _jsx(_components.code, { children: "+" }), ", ", _jsx(_components.code, { children: "-" }), ", ", _jsx(_components.code, { children: "*" }), ", ", _jsx(_components.code, { children: "/" }), ")."] }), "\n"] }), _jsxs(_components.p, { children: ["The tree structure captures the ", _jsx(_components.strong, { children: "precedence and associativity" }), " of operators."] }), _jsxs(_components.h3, { children: ["🎯 Example: Expression Tree for ", _jsx(_components.code, { children: "A + B * C" })] }), _jsxs(_components.p, { children: ["The operator ", _jsx(_components.code, { children: "*" }), " has higher precedence than ", _jsx(_components.code, { children: "+" }), ", so it is evaluated first. The expression tree looks like:"] }), _jsx(_components.pre, { children: _jsx(_components.code, { children: " +\n / \\\n A *\n / \\\n B C\n" }) }), _jsxs(_components.ul, { children: ["\n", _jsxs(_components.li, { children: [_jsx(_components.strong, { children: "Root" }), " = ", _jsx(_components.code, { children: "+" }), " (lowest precedence operator at top)"] }), "\n", _jsxs(_components.li, { children: [_jsxs(_components.strong, { children: ["Left child of ", _jsx(_components.code, { children: "+" })] }), " = ", _jsx(_components.code, { children: "A" }), " (operand)"] }), "\n", _jsxs(_components.li, { children: [_jsxs(_components.strong, { children: ["Right child of ", _jsx(_components.code, { children: "+" })] }), " = ", _jsx(_components.code, { children: "*" }), " (sub-expression ", _jsx(_components.code, { children: "B * C" }), ")"] }), "\n", _jsxs(_components.li, { children: [_jsxs(_components.strong, { children: ["Children of ", _jsx(_components.code, { children: "*" })] }), " = ", _jsx(_components.code, { children: "B" }), " and ", _jsx(_components.code, { children: "C" }), " (operands)"] }), "\n"] }), _jsx(Remember, { children: _jsxs(_components.p, { children: ["In an Expression Tree, the operator with the ", _jsx(_components.strong, { children: "lowest precedence" }), " always appears at the ", _jsx(_components.strong, { children: "root" }), ", and operators with ", _jsx(_components.strong, { children: "higher precedence" }), " appear ", _jsx(_components.strong, { children: "deeper" }), " in the tree."] }) })] })] }), _jsxs(QAQuestion, { marks: 4, children: [_jsx(Prompt, { children: "Explain the properties of a Heap data structure and differentiate between Min Heap and Max Heap with examples." }), _jsxs(Answer, { children: [_jsx(_components.h3, { children: "🎯 What is a Heap?" }), _jsxs(_components.p, { children: ["A ", _jsx(_components.strong, { children: "Heap" }), " is a ", _jsx(_components.strong, { children: "complete binary tree" }), " that satisfies the ", _jsx(_components.strong, { children: "heap property" }), ". It is commonly implemented using an ", _jsx(_components.strong, { children: "array" }), " (not pointers)."] }), _jsx(_components.h3, { children: "📝 Properties of a Heap" }), _jsxs(_components.ol, { children: ["\n", _jsxs(_components.li, { children: ["It must be a ", _jsx(_components.strong, { children: "complete binary tree" }), " — all levels are completely filled except possibly the last level, which is filled from ", _jsx(_components.strong, { children: "left to right" }), "."] }), "\n", _jsxs(_components.li, { children: ["It follows the ", _jsx(_components.strong, { children: "heap ordering property" }), " (either Min Heap or Max Heap)."] }), "\n"] }), _jsx(_components.p, { children: _jsx(_components.strong, { children: "Array Representation:" }) }), _jsxs(_components.ul, { children: ["\n", _jsxs(_components.li, { children: ["If a node is at index ", _jsx(_components.code, { children: "i" }), ", then:", "\n", _jsxs(_components.ul, { children: ["\n", _jsxs(_components.li, { children: [_jsx(_components.strong, { children: "Left child" }), " → at index ", _jsx(_components.code, { children: "2*i + 1" })] }), "\n", _jsxs(_components.li, { children: [_jsx(_components.strong, { children: "Right child" }), " → at index ", _jsx(_components.code, { children: "2*i + 2" })] }), "\n", _jsxs(_components.li, { children: [_jsx(_components.strong, { children: "Parent" }), " → at index ", _jsx(_components.code, { children: "(i - 1) / 2" })] }), "\n"] }), "\n"] }), "\n"] }), _jsx(_components.h3, { children: "🔄 Min Heap vs Max Heap" }), _jsx(ComparisonTable, { title: "Min Heap vs Max Heap", children: _jsxs(_components.table, { children: [_jsx(_components.thead, { children: _jsxs(_components.tr, { children: [_jsx(_components.th, { children: "Aspect" }), _jsx(_components.th, { children: "Min Heap" }), _jsx(_components.th, { children: "Max Heap" })] }) }), _jsxs(_components.tbody, { children: [_jsxs(_components.tr, { children: [_jsx(_components.td, { children: _jsx(_components.strong, { children: "Heap Property" }) }), _jsxs(_components.td, { children: ["Parent node is always ", _jsx(_components.strong, { children: "smaller than or equal to" }), " its children"] }), _jsxs(_components.td, { children: ["Parent node is always ", _jsx(_components.strong, { children: "greater than or equal to" }), " its children"] })] }), _jsxs(_components.tr, { children: [_jsx(_components.td, { children: _jsx(_components.strong, { children: "Root Element" }) }), _jsxs(_components.td, { children: [_jsx(_components.strong, { children: "Minimum" }), " element of the heap"] }), _jsxs(_components.td, { children: [_jsx(_components.strong, { children: "Maximum" }), " element of the heap"] })] }), _jsxs(_components.tr, { children: [_jsx(_components.td, { children: _jsx(_components.strong, { children: "Example Array" }) }), _jsx(_components.td, { children: _jsx(_components.code, { children: "[2, 5, 8, 10, 12]" }) }), _jsx(_components.td, { children: _jsx(_components.code, { children: "[12, 10, 8, 5, 2]" }) })] }), _jsxs(_components.tr, { children: [_jsx(_components.td, { children: _jsx(_components.strong, { children: "Use Case" }) }), _jsx(_components.td, { children: "Priority Queue (smallest first), Dijkstra's algorithm" }), _jsx(_components.td, { children: "Priority Queue (largest first), Heap Sort" })] })] })] }) }), _jsx(_components.h3, { children: "🎯 Example" }), _jsxs(_components.p, { children: [_jsx(_components.strong, { children: "Max Heap" }), " represented as array ", _jsx(_components.code, { children: "[90, 70, 80, 50, 60]" }), ":"] }), _jsx(_components.pre, { children: _jsx(_components.code, { children: " 90\n / \\\n 70 80\n / \\\n 50 60\n" }) }), _jsx(_components.p, { children: "Here, every parent is greater than or equal to its children — so the Max Heap property is satisfied." }), _jsx(Remember, { children: _jsxs(_components.p, { children: ["A Heap is ", _jsx(_components.strong, { children: "NOT" }), " a Binary Search Tree (BST). The left child of a node can be greater than the right child — only the ", _jsx(_components.strong, { children: "parent-child ordering" }), " matters, not the left-right ordering among siblings."] }) })] })] }), _jsxs(QAQuestion, { marks: 6, children: [_jsx(Prompt, { children: "Explain the Heapify process with an example. Also write the C function to perform Max Heapify on an array-based binary heap." }), _jsxs(Answer, { children: [_jsx(_components.h3, { children: "🎯 What is Heapify?" }), _jsxs(_components.p, { children: [_jsx(_components.strong, { children: "Heapify" }), " is the process of converting a binary tree (or a subtree rooted at a given node) into a valid Heap. It is the core operation used in ", _jsx(_components.strong, { children: "Heap Sort" }), " and ", _jsx(_components.strong, { children: "Priority Queue" }), " implementations."] }), _jsxs(_components.p, { children: ["If a node violates the Max Heap property (i.e., a child is larger than its parent), Heapify ", _jsx(_components.strong, { children: "sifts the node down" }), " by swapping it with the largest of its children until the property is restored."] }), _jsx(_components.h3, { children: "📝 Heapify Process — Step by Step" }), _jsxs(_components.p, { children: ["Consider the following array which is ", _jsx(_components.strong, { children: "NOT" }), " a valid Max Heap:"] }), _jsx(_components.pre, { children: _jsx(_components.code, { children: "[40, 10, 80, 50, 60, 70]\n" }) }), _jsx(_components.p, { children: "Tree representation:" }), _jsx(_components.pre, { children: _jsx(_components.code, { children: " 40\n / \\\n 10 80\n / \\ / \\\n 50 60 70\n" }) }), _jsxs(_components.p, { children: [_jsx(_components.strong, { children: "Problem:" }), " Root ", _jsx(_components.code, { children: "40" }), " is smaller than its children ", _jsx(_components.code, { children: "10" }), " and ", _jsx(_components.code, { children: "80" }), ". Wait — actually ", _jsx(_components.code, { children: "40 > 10" }), ", but ", _jsx(_components.code, { children: "40 < 80" }), ". So the Max Heap property is violated at the root."] }), _jsx(_components.p, { children: _jsxs(_components.strong, { children: ["Applying Max Heapify at index ", _jsx(_components.code, { children: "0" }), " (root):"] }) }), _jsxs(_components.ul, { children: ["\n", _jsxs(_components.li, { children: [_jsx(_components.strong, { children: "Step 1:" }), " Compare root ", _jsx(_components.code, { children: "40" }), " with its children ", _jsx(_components.code, { children: "10" }), " (index 1) and ", _jsx(_components.code, { children: "80" }), " (index 2). The largest is ", _jsx(_components.code, { children: "80" }), "."] }), "\n", _jsxs(_components.li, { children: [_jsx(_components.strong, { children: "Step 2:" }), " Since ", _jsx(_components.code, { children: "80 > 40" }), ", ", _jsx(_components.strong, { children: "swap" }), " ", _jsx(_components.code, { children: "40" }), " and ", _jsx(_components.code, { children: "80" }), "."] }), "\n"] }), _jsx(_components.pre, { children: _jsx(_components.code, { children: "[80, 10, 40, 50, 60, 70]\n" }) }), _jsx(_components.pre, { children: _jsx(_components.code, { children: " 80\n / \\\n 10 40\n / \\ / \\\n 50 60 70\n" }) }), _jsxs(_components.ul, { children: ["\n", _jsxs(_components.li, { children: [_jsx(_components.strong, { children: "Step 3:" }), " Now check index ", _jsx(_components.code, { children: "2" }), " (where ", _jsx(_components.code, { children: "40" }), " moved). Its children are ", _jsx(_components.code, { children: "70" }), " (index 5). Since ", _jsx(_components.code, { children: "70 > 40" }), ", ", _jsx(_components.strong, { children: "swap" }), " again."] }), "\n"] }), _jsx(_components.pre, { children: _jsx(_components.code, { children: "[80, 10, 70, 50, 60, 40]\n" }) }), _jsx(_components.pre, { children: _jsx(_components.code, { children: " 80\n / \\\n 10 70\n / \\ / \\\n 50 60 40\n" }) }), _jsxs(_components.ul, { children: ["\n", _jsxs(_components.li, { children: [_jsx(_components.strong, { children: "Step 4:" }), " Node ", _jsx(_components.code, { children: "40" }), " at index 5 has no children. ", _jsx(_components.strong, { children: "Heapify stops." }), " The tree is now a valid Max Heap. ✅"] }), "\n"] }), _jsx(_components.h3, { children: "💻 C Function for Max Heapify" }), _jsx(_components.pre, { children: _jsx(_components.code, { className: "language-c", children: "// Heapify a subtree rooted at index 'i'\n// 'n' is the size of the heap\nvoid maxHeapify(int arr[], int n, int i)\n{\n int largest = i; // Initialize largest as root\n int left = 2 * i + 1; // Left child index\n int right = 2 * i + 2; // Right child index\n\n // If left child exists and is greater than root\n if (left < n && arr[left] > arr[largest])\n largest = left;\n\n // If right child exists and is greater than current largest\n if (right < n && arr[right] > arr[largest])\n largest = right;\n\n // If largest is not root, swap and continue heapifying\n if (largest != i)\n {\n int temp = arr[i];\n arr[i] = arr[largest];\n arr[largest] = temp;\n\n // Recursively heapify the affected subtree\n maxHeapify(arr, n, largest);\n }\n}\n" }) }), _jsx(_components.h3, { children: "🔍 Build Max Heap — Using Heapify" }), _jsxs(_components.p, { children: ["To build a complete Max Heap from an unsorted array, call ", _jsx(_components.code, { children: "maxHeapify" }), " from the ", _jsx(_components.strong, { children: "last non-leaf node" }), " down to the root:"] }), _jsx(_components.pre, { children: _jsx(_components.code, { className: "language-c", children: "void buildMaxHeap(int arr[], int n)\n{\n // Last non-leaf node index = (n / 2) - 1\n int i;\n for (i = (n / 2) - 1; i >= 0; i--)\n {\n maxHeapify(arr, n, i);\n }\n}\n" }) }), _jsx(Remember, { children: _jsxs(_components.p, { children: [_jsx(_components.strong, { children: "Heapify Time Complexity:" }), " ", _jsx(_components.span, { className: "katex", children: _jsx(_components.span, { className: "katex-html", "aria-hidden": "true", children: _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.0278em" }, children: "O" }), _jsx(_components.span, { className: "mopen", children: "(" }), _jsxs(_components.span, { className: "mop", children: ["lo", _jsx(_components.span, { style: { marginRight: "0.0139em" }, children: "g" })] }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.1667em" } }), _jsx(_components.span, { className: "mord mathnormal", children: "n" }), _jsx(_components.span, { className: "mclose", children: ")" })] }) }) }), " — because in the worst case, the node may travel from root to the last level. ", _jsx(_components.strong, { children: "Build Heap" }), " using bottom-up Heapify runs in ", _jsx(_components.span, { className: "katex", children: _jsx(_components.span, { className: "katex-html", "aria-hidden": "true", children: _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.0278em" }, children: "O" }), _jsx(_components.span, { className: "mopen", children: "(" }), _jsx(_components.span, { className: "mord mathnormal", children: "n" }), _jsx(_components.span, { className: "mclose", children: ")" })] }) }) }), " total time, not ", _jsx(_components.span, { className: "katex", children: _jsx(_components.span, { className: "katex-html", "aria-hidden": "true", children: _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.0278em" }, children: "O" }), _jsx(_components.span, { className: "mopen", children: "(" }), _jsx(_components.span, { className: "mord mathnormal", children: "n" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.1667em" } }), _jsxs(_components.span, { className: "mop", children: ["lo", _jsx(_components.span, { style: { marginRight: "0.0139em" }, children: "g" })] }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.1667em" } }), _jsx(_components.span, { className: "mord mathnormal", children: "n" }), _jsx(_components.span, { className: "mclose", children: ")" })] }) }) }), "."] }) })] })] })] }) }), "\n", _jsxs(Assessment, { topicId: "6.3", children: [_jsx(MCQ, { questions: [{ "id": "14136aef-fbe0-4905-9411-2222aa5fc834", "q": "In an expression tree, the leaf nodes represent:", "options": ["Operators", "Operands", "Variables only", "Constants only"], "answer": 1, "hint": "Think about what symbols appear at the bottom of an expression tree.", "explanation": "Leaf nodes in an expression tree represent the operands such as numbers or variables of the expression." }, { "id": "eebc2614-7085-4151-b585-57889485bc76", "q": "The internal nodes of an expression tree represent:", "options": ["Operands", "Operators", "Leaf values", "Memory addresses"], "answer": 1, "hint": "Consider what symbols connect the operands in an arithmetic expression.", "explanation": "Internal nodes in an expression tree represent the operators that combine two sub-expressions (operands)." }, { "id": "7bf51f01-be55-43bc-96b0-267789ad2cbc", "q": "Which traversal of an expression tree gives the infix form of the expression?", "options": ["Pre-order", "Post-order", "In-order", "Level-order"], "answer": 2, "hint": "Recall the three standard tree traversals and what each produces for expressions.", "explanation": "In-order traversal (left-root-right) of an expression tree produces the infix notation, where operators appear between their operands." }, { "id": "d322d0bf-c93b-465b-931a-74bc934c35c7", "q": "Which traversal of an expression tree gives the postfix form of the expression?", "options": ["Pre-order", "In-order", "Post-order", "Level-order"], "answer": 2, "hint": "Post-order means visiting the left subtree, then the right subtree, then the root.", "explanation": "Post-order traversal (left-right-root) of an expression tree gives the postfix notation, also known as Reverse Polish Notation." }, { "id": "648b652a-2667-4320-bc96-8faa61aca37c", "q": "In a Min Heap, the value of every node must be:", "options": ["Greater than its parent", "Less than or equal to its parent", "Equal to its children", "Greater than all descendants"], "answer": 1, "hint": "Think about the ordering property that keeps the minimum element at the root.", "explanation": "In a Min Heap, each node's value is less than or equal to its parent's value, ensuring the root always holds the minimum element in the heap." }, { "id": "c7a48d10-a4a6-477e-adf9-fabe5e7dd061", "q": "In a 0-based array representation of a heap, the left child of a node at index i is at:", "options": ["$2i$", "$2i+1$", "$2i+2$", "$i+1$"], "answer": 1, "hint": "For a 0-based array, children are placed at predictable even and odd positions.", "explanation": "For 0-based indexing, the left child of a node at index i is located at index 2i+1 in the array." }, { "id": "4205f9f9-fbc8-4aa5-97ea-ea0b6bd3ab17", "q": "In a 0-based array representation of a heap, the right child of a node at index i is at:", "options": ["$2i$", "$2i+1$", "$2i+2$", "$2(i+1)$"], "answer": 2, "hint": "The right child is typically one position after the left child in array-based heap storage.", "explanation": "For 0-based indexing, the right child of a node at index i is located at index 2i+2 in the array." }, { "id": "aac31e0b-78e8-4e30-9445-c4bd8be5da64", "q": "In a 0-based array representation of a heap, the parent of a node at index i is at:", "options": ["$i/2$", "$(i-1)/2$", "$(i+1)/2$", "$2i$"], "answer": 1, "hint": "To find a parent, reverse the formula used to find children positions.", "explanation": "For 0-based indexing, the parent of a node at index i is located at index (i-1)/2 using integer division." }, { "id": "60232fe2-1377-479d-8b10-ecd7362c0c57", "q": "The time complexity to build a heap from an unsorted array of n elements is:", "options": ["$O(n)$", "$O(n \\log n)$", "$O(\\log n)$", "$O(n^2)$"], "answer": 0, "hint": "Building a heap using the bottom-up approach is more efficient than performing n individual insertions.", "explanation": "Although inserting one element takes O(log n), building a heap from an unsorted array bottom-up takes O(n) total time due to decreasing work at lower levels of the tree." }, { "id": "ca95157d-2bd2-48e6-ba51-7b7b357fcb3b", "q": "A heap data structure is always a:", "options": ["Complete binary tree", "Full binary tree", "Perfect binary tree", "Binary search tree"], "answer": 0, "hint": "Think about the structural property that allows heaps to be stored efficiently in arrays.", "explanation": "A heap is always a complete binary tree, meaning all levels are fully filled except possibly the last level, which is filled from left to right without any gaps." }], topicId: "6.3" }), _jsx(ContentAttribution, { sourceTitle: "Curriculum Reference", sourceUrl: "https://learningway.in", professor: "Faculty Review Team", model: "Curriculum AI", seoTitle: "Expression Tree and Heap", seoDesc: "Master Expression Tree and Heap with comprehensive notes, real-world examples, and practice quiz on LearningWay.", seoKeywords: "expression tree and heap, expression tree and heap notes, expression tree and heap examples, diploma engineering notes, practice quiz, learningway" })] })] }); } function MDXContent(props = {}) { const {wrapper: MDXLayout} = { ..._provideComponents(), ...props.components }; return MDXLayout ? _jsx(MDXLayout, { ...props, children: _jsx(_createMdxContent, { ...props }) }) : _createMdxContent(props); } return { default: MDXContent }; function _missingMdxReference(id, component) { throw new Error("Expected " + (component ? "component" : "object") + " `" + id + "` to be defined: you likely forgot to import, pass, or provide it."); }