var Component=(()=>{var d=Object.create;var l=Object.defineProperty;var m=Object.getOwnPropertyDescriptor;var h=Object.getOwnPropertyNames;var u=Object.getPrototypeOf,N=Object.prototype.hasOwnProperty;var k=(a,n)=>()=>(n||a((n={exports:{}}).exports,n),n.exports),b=(a,n)=>{for(var s in n)l(a,s,{get:n[s],enumerable:!0})},t=(a,n,s,i)=>{if(n&&typeof n=="object"||typeof n=="function")for(let c of h(n))!N.call(a,c)&&c!==s&&l(a,c,{get:()=>n[c],enumerable:!(i=m(n,c))||i.enumerable});return a};var g=(a,n,s)=>(s=a!=null?d(u(a)):{},t(n||!a||!a.__esModule?l(s,"default",{value:a,enumerable:!0}):s,a)),f=a=>t(l({},"__esModule",{value:!0}),a);var o=k((O,r)=>{r.exports=_jsx_runtime});var v={};b(v,{default:()=>x,frontmatter:()=>y});var e=g(o()),y={title:"Heap sort",slug:"heapsort",description:"Master Heapsort with this concise guide, covering its O(n log n) time complexity and step-by-step implementation in Python, Java, C++, Go, and Rust. Perfect for developers seeking a deep understanding of Heapsort across multiple languages.",image:"https://cdn.procoding.org/datastructures/heap/heapsort/heapsort.png",publishedAt:"2024-08-30",updatedAt:"2024-08-30",isPublished:!0,category:"Data Structures",metadescription:"Master Heapsort with this concise guide, covering its O(n log n) time complexity and step-by-step implementation in Python, Java, C++, Go, and Rust. Perfect for developers seeking a deep understanding of Heapsort across multiple languages.",keywords:"heap,heapify,sort,heapsort,datastructures",subcategory:"heap",tags:["heap","heapify","sort","heapsort","datastructures"],author:"abhishek",id:"aff0d442-da88-4f9e-a7e3-ab8dd6055cea"};function p(a){let n=Object.assign({p:"p",img:"img",h2:"h2",ol:"ol",li:"li",strong:"strong",h3:"h3",code:"code",pre:"pre",span:"span",ul:"ul"},a.components);return(0,e.jsxs)(e.Fragment,{children:[(0,e.jsx)(n.p,{children:(0,e.jsx)(n.img,{src:"https://cdn.procoding.org/datastructures/heap/heapsort/heapsort.png",alt:"Heapsort",title:"Heapsort"})}),` `,(0,e.jsx)(n.p,{children:"Since we know about Heap and Heapify now, we can easily get the minimum (using min-heap) and maximum (using max-heap). So, if we have an array then we can pull the minimum data and keep inserting it in another array and continuously heapify down (percolate down) to maintain the heap property then we can get a sorted array in another array."}),` `,(0,e.jsx)(n.p,{children:"The time complexity of this solution will be O(n log n) because each heapify down operation will take log n time and we will do this for n times which is the same as other sorting algorithms."}),` `,(0,e.jsx)(n.p,{children:"But we are using extra space in the form of another array to keep a sorted array. So the space complexity will be O(n)."}),` `,(0,e.jsx)(n.p,{children:"We can remove the extra space used and do the sorting in place which will be a proper heapsort."}),` `,(0,e.jsx)(n.h2,{children:"Introduction to Heapsort"}),` `,(0,e.jsx)(n.p,{children:"Heapsort is an efficient, in-place sorting algorithm that leverages the properties of binary heaps. It can be used to sort an array of elements in either ascending or descending order, depending on whether a min-heap or a max-heap is used. Heapsort is not a stable sort, meaning it does not preserve the relative order of equal elements. However, it has a consistent time complexity of O(nlogn) for all cases."}),` `,(0,e.jsx)(n.p,{children:"As we discussed earlier we know the sorting using heap. We aim to reduce the extra space used and put the changes in place. Instead of putting the sorted elements in a separate array, we will maintain the partition in the same array to identify the sorted part and continuously apply heapify algo on the rest of the unsorted part to get max and put it into the end after each iteration."}),` `,(0,e.jsx)(n.h2,{children:"Heapsort Algorithm"}),` `,(0,e.jsx)(n.p,{children:"Heapsort uses a max-heap to sort an array in ascending order or a min-heap for descending order. The algorithm consists of two main phases:"}),` `,(0,e.jsxs)(n.ol,{children:[` `,(0,e.jsxs)(n.li,{children:[(0,e.jsx)(n.strong,{children:"Build the Heap"}),": Convert the array into a heap. In a max-heap, the largest element will be at the root."]}),` `,(0,e.jsxs)(n.li,{children:[(0,e.jsx)(n.strong,{children:"Sort the Array"}),": Repeatedly extract the root (the largest element in the case of a max-heap), swap it with the last element, reduce the heap size, and heapify the root to maintain the heap property."]}),` `]}),` `,(0,e.jsx)(n.h3,{children:"Step-by-Step Process"}),` `,(0,e.jsxs)(n.ol,{children:[` `,(0,e.jsxs)(n.li,{children:[(0,e.jsx)(n.strong,{children:"Heapify the Array"}),": Start by building a max-heap from the array. This is done by applying the heapify operation to each non-leaf node, starting from the last non-leaf node up to the root."]}),` `,(0,e.jsxs)(n.li,{children:[(0,e.jsx)(n.strong,{children:"Sort the Array"}),": After building the heap, the largest element is at the root. Swap it with the last element of the array and reduce the size of the heap by one. Then, heapify the root again to ensure the max-heap property is maintained. Repeat this process until the heap size is reduced to one."]}),` `]}),` `,(0,e.jsx)(n.p,{children:"Let's take the example of this array and sort the elements using heapsort"}),` `,(0,e.jsx)(n.p,{children:(0,e.jsx)(n.img,{src:"https://cdn.procoding.org/datastructures/heap/heapsort/heapsort1.png",alt:"Heapsort step 1",title:"Heapsort step 1"})}),` `,(0,e.jsx)(n.p,{children:"On applying max-heapify, we will get elements in ascending order; if we apply min-heapify, we will get elements in descending order. We will apply max-heapify to get elements in ascending order."}),` `,(0,e.jsxs)(n.p,{children:["The first step is to apply max-heapify operation on the whole array i.e., from ",(0,e.jsx)(n.code,{children:"n/2"})," to ",(0,e.jsx)(n.code,{children:"0"})," to heapify the array and get the highest element at the 0th index. After this the array will get the heap structures."]}),` `,(0,e.jsxs)(n.p,{children:["Once we get the highest element on the 0th index, then swap it with the elemental at last index. We will be maintaining the sorted elements at the end. And heap area is from index ",(0,e.jsx)(n.code,{children:"0"})," to ",(0,e.jsx)(n.code,{children:"3"}),"."]}),` `,(0,e.jsx)(n.p,{children:(0,e.jsx)(n.img,{src:"https://cdn.procoding.org/datastructures/heap/heapsort/heapsort2.png",alt:"Heapsort step 2",title:"Heapsort step 2"})}),` `,(0,e.jsx)(n.p,{children:"Now the last index is sorted. From this step, we will heapify the element at the 0th index only to get the maximum element at the 0th index and swap it with the last index based on the partition of the sorted array we are maintaining. After each step, we are sure that the element at the 0th index is only disturbed that's why will just heapify that element and we will get the next maximum on the 0th index."}),` `,(0,e.jsx)(n.p,{children:(0,e.jsx)(n.img,{src:"https://cdn.procoding.org/datastructures/heap/heapsort/heapsort3.png",alt:"Heapsort step 3",title:"Heapsort step 3"})}),` `,(0,e.jsx)(n.p,{children:"Now elements from 3 to 4 are sorted and we will just focus on elements from 0 to 2. Apply heapify on the 0th index again to get maximum."}),` `,(0,e.jsx)(n.p,{children:(0,e.jsx)(n.img,{src:"https://cdn.procoding.org/datastructures/heap/heapsort/heapsort4.png",alt:"Heapsort step 4",title:"Heapsort step 4"})}),` `,(0,e.jsx)(n.p,{children:"Now elements from index 2 to 4 are sorted. Our focus will be on 0 to 1."}),` `,(0,e.jsx)(n.p,{children:(0,e.jsx)(n.img,{src:"https://cdn.procoding.org/datastructures/heap/heapsort/heapsort5.png",alt:"Heapsort step 5",title:"Heapsort step 5"})}),` `,(0,e.jsx)(n.p,{children:"After this step elements from 1 to 4 are sorted and we only only have one element left at the 0th index which is sorted itself. So, we have a final sorted array."}),` `,(0,e.jsx)(n.p,{children:(0,e.jsx)(n.img,{src:"https://cdn.procoding.org/datastructures/heap/heapsort/heapsort6.png",alt:"Heapsort step 6",title:"Heapsort step 6"})}),` `,(0,e.jsx)(n.h2,{children:"Heapsort Implementation"}),` `,(0,e.jsxs)("details",{className:"code-block",children:[(0,e.jsx)("summary",{children:"Python"}),(0,e.jsx)(n.pre,{className:"language-python",children:(0,e.jsxs)(n.code,{className:"language-python code-highlight",children:[(0,e.jsxs)(n.span,{className:"code-line line-number",line:"1",children:[(0,e.jsx)(n.span,{className:"token keyword",children:"def"})," ",(0,e.jsx)(n.span,{className:"token function",children:"heapify"}),(0,e.jsx)(n.span,{className:"token punctuation",children:"("}),"arr",(0,e.jsx)(n.span,{className:"token punctuation",children:","})," n",(0,e.jsx)(n.span,{className:"token punctuation",children:","})," i",(0,e.jsx)(n.span,{className:"token punctuation",children:")"}),(0,e.jsx)(n.span,{className:"token punctuation",children:":"}),` `]}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"2",children:[" largest ",(0,e.jsx)(n.span,{className:"token operator",children:"="}),` i `]}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"3",children:[" left ",(0,e.jsx)(n.span,{className:"token operator",children:"="})," ",(0,e.jsx)(n.span,{className:"token number",children:"2"})," ",(0,e.jsx)(n.span,{className:"token operator",children:"*"})," i ",(0,e.jsx)(n.span,{className:"token operator",children:"+"})," ",(0,e.jsx)(n.span,{className:"token number",children:"1"}),` `]}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"4",children:[" right ",(0,e.jsx)(n.span,{className:"token operator",children:"="})," ",(0,e.jsx)(n.span,{className:"token number",children:"2"})," ",(0,e.jsx)(n.span,{className:"token operator",children:"*"})," i ",(0,e.jsx)(n.span,{className:"token operator",children:"+"})," ",(0,e.jsx)(n.span,{className:"token number",children:"2"}),` `]}),(0,e.jsx)(n.span,{className:"code-line line-number",line:"5",children:` `}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"6",children:[" ",(0,e.jsx)(n.span,{className:"token keyword",children:"if"})," left ",(0,e.jsx)(n.span,{className:"token operator",children:"<"})," n ",(0,e.jsx)(n.span,{className:"token keyword",children:"and"})," arr",(0,e.jsx)(n.span,{className:"token punctuation",children:"["}),"i",(0,e.jsx)(n.span,{className:"token punctuation",children:"]"})," ",(0,e.jsx)(n.span,{className:"token operator",children:"<"})," arr",(0,e.jsx)(n.span,{className:"token punctuation",children:"["}),"left",(0,e.jsx)(n.span,{className:"token punctuation",children:"]"}),(0,e.jsx)(n.span,{className:"token punctuation",children:":"}),` `]}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"7",children:[" largest ",(0,e.jsx)(n.span,{className:"token operator",children:"="}),` left `]}),(0,e.jsx)(n.span,{className:"code-line line-number",line:"8",children:` `}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"9",children:[" ",(0,e.jsx)(n.span,{className:"token keyword",children:"if"})," right ",(0,e.jsx)(n.span,{className:"token operator",children:"<"})," n ",(0,e.jsx)(n.span,{className:"token keyword",children:"and"})," arr",(0,e.jsx)(n.span,{className:"token punctuation",children:"["}),"largest",(0,e.jsx)(n.span,{className:"token punctuation",children:"]"})," ",(0,e.jsx)(n.span,{className:"token operator",children:"<"})," arr",(0,e.jsx)(n.span,{className:"token punctuation",children:"["}),"right",(0,e.jsx)(n.span,{className:"token punctuation",children:"]"}),(0,e.jsx)(n.span,{className:"token punctuation",children:":"}),` `]}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"10",children:[" largest ",(0,e.jsx)(n.span,{className:"token operator",children:"="}),` right `]}),(0,e.jsx)(n.span,{className:"code-line line-number",line:"11",children:` `}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"12",children:[" ",(0,e.jsx)(n.span,{className:"token keyword",children:"if"})," largest ",(0,e.jsx)(n.span,{className:"token operator",children:"!="})," i",(0,e.jsx)(n.span,{className:"token punctuation",children:":"}),` `]}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"13",children:[" arr",(0,e.jsx)(n.span,{className:"token punctuation",children:"["}),"i",(0,e.jsx)(n.span,{className:"token punctuation",children:"]"}),(0,e.jsx)(n.span,{className:"token punctuation",children:","})," arr",(0,e.jsx)(n.span,{className:"token punctuation",children:"["}),"largest",(0,e.jsx)(n.span,{className:"token punctuation",children:"]"})," ",(0,e.jsx)(n.span,{className:"token operator",children:"="})," arr",(0,e.jsx)(n.span,{className:"token punctuation",children:"["}),"largest",(0,e.jsx)(n.span,{className:"token punctuation",children:"]"}),(0,e.jsx)(n.span,{className:"token punctuation",children:","})," arr",(0,e.jsx)(n.span,{className:"token punctuation",children:"["}),"i",(0,e.jsx)(n.span,{className:"token punctuation",children:"]"}),` `]}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"14",children:[" heapify",(0,e.jsx)(n.span,{className:"token punctuation",children:"("}),"arr",(0,e.jsx)(n.span,{className:"token punctuation",children:","})," n",(0,e.jsx)(n.span,{className:"token punctuation",children:","})," largest",(0,e.jsx)(n.span,{className:"token punctuation",children:")"}),` `]}),(0,e.jsx)(n.span,{className:"code-line line-number",line:"15",children:` `}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"16",children:[(0,e.jsx)(n.span,{className:"token keyword",children:"def"})," ",(0,e.jsx)(n.span,{className:"token function",children:"heapsort"}),(0,e.jsx)(n.span,{className:"token punctuation",children:"("}),"arr",(0,e.jsx)(n.span,{className:"token punctuation",children:")"}),(0,e.jsx)(n.span,{className:"token punctuation",children:":"}),` `]}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"17",children:[" n ",(0,e.jsx)(n.span,{className:"token operator",children:"="})," ",(0,e.jsx)(n.span,{className:"token builtin",children:"len"}),(0,e.jsx)(n.span,{className:"token punctuation",children:"("}),"arr",(0,e.jsx)(n.span,{className:"token punctuation",children:")"}),` `]}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"18",children:[" ",(0,e.jsx)(n.span,{className:"token keyword",children:"for"})," i ",(0,e.jsx)(n.span,{className:"token keyword",children:"in"})," ",(0,e.jsx)(n.span,{className:"token builtin",children:"range"}),(0,e.jsx)(n.span,{className:"token punctuation",children:"("}),"n ",(0,e.jsx)(n.span,{className:"token operator",children:"//"})," ",(0,e.jsx)(n.span,{className:"token number",children:"2"})," ",(0,e.jsx)(n.span,{className:"token operator",children:"-"})," ",(0,e.jsx)(n.span,{className:"token number",children:"1"}),(0,e.jsx)(n.span,{className:"token punctuation",children:","})," ",(0,e.jsx)(n.span,{className:"token operator",children:"-"}),(0,e.jsx)(n.span,{className:"token number",children:"1"}),(0,e.jsx)(n.span,{className:"token punctuation",children:","})," ",(0,e.jsx)(n.span,{className:"token operator",children:"-"}),(0,e.jsx)(n.span,{className:"token number",children:"1"}),(0,e.jsx)(n.span,{className:"token punctuation",children:")"}),(0,e.jsx)(n.span,{className:"token punctuation",children:":"}),` `]}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"19",children:[" heapify",(0,e.jsx)(n.span,{className:"token punctuation",children:"("}),"arr",(0,e.jsx)(n.span,{className:"token punctuation",children:","})," n",(0,e.jsx)(n.span,{className:"token punctuation",children:","})," i",(0,e.jsx)(n.span,{className:"token punctuation",children:")"}),` `]}),(0,e.jsx)(n.span,{className:"code-line line-number",line:"20",children:` `}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"21",children:[" ",(0,e.jsx)(n.span,{className:"token keyword",children:"for"})," i ",(0,e.jsx)(n.span,{className:"token keyword",children:"in"})," ",(0,e.jsx)(n.span,{className:"token builtin",children:"range"}),(0,e.jsx)(n.span,{className:"token punctuation",children:"("}),"n ",(0,e.jsx)(n.span,{className:"token operator",children:"-"})," ",(0,e.jsx)(n.span,{className:"token number",children:"1"}),(0,e.jsx)(n.span,{className:"token punctuation",children:","})," ",(0,e.jsx)(n.span,{className:"token number",children:"0"}),(0,e.jsx)(n.span,{className:"token punctuation",children:","})," ",(0,e.jsx)(n.span,{className:"token operator",children:"-"}),(0,e.jsx)(n.span,{className:"token number",children:"1"}),(0,e.jsx)(n.span,{className:"token punctuation",children:")"}),(0,e.jsx)(n.span,{className:"token punctuation",children:":"}),` `]}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"22",children:[" arr",(0,e.jsx)(n.span,{className:"token punctuation",children:"["}),"i",(0,e.jsx)(n.span,{className:"token punctuation",children:"]"}),(0,e.jsx)(n.span,{className:"token punctuation",children:","})," arr",(0,e.jsx)(n.span,{className:"token punctuation",children:"["}),(0,e.jsx)(n.span,{className:"token number",children:"0"}),(0,e.jsx)(n.span,{className:"token punctuation",children:"]"})," ",(0,e.jsx)(n.span,{className:"token operator",children:"="})," arr",(0,e.jsx)(n.span,{className:"token punctuation",children:"["}),(0,e.jsx)(n.span,{className:"token number",children:"0"}),(0,e.jsx)(n.span,{className:"token punctuation",children:"]"}),(0,e.jsx)(n.span,{className:"token punctuation",children:","})," arr",(0,e.jsx)(n.span,{className:"token punctuation",children:"["}),"i",(0,e.jsx)(n.span,{className:"token punctuation",children:"]"}),` `]}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"23",children:[" heapify",(0,e.jsx)(n.span,{className:"token punctuation",children:"("}),"arr",(0,e.jsx)(n.span,{className:"token punctuation",children:","})," i",(0,e.jsx)(n.span,{className:"token punctuation",children:","})," ",(0,e.jsx)(n.span,{className:"token number",children:"0"}),(0,e.jsx)(n.span,{className:"token punctuation",children:")"}),` `]}),(0,e.jsx)(n.span,{className:"code-line line-number",line:"24",children:` `}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"25",children:["arr ",(0,e.jsx)(n.span,{className:"token operator",children:"="})," ",(0,e.jsx)(n.span,{className:"token punctuation",children:"["}),(0,e.jsx)(n.span,{className:"token number",children:"4"}),(0,e.jsx)(n.span,{className:"token punctuation",children:","})," ",(0,e.jsx)(n.span,{className:"token number",children:"10"}),(0,e.jsx)(n.span,{className:"token punctuation",children:","})," ",(0,e.jsx)(n.span,{className:"token number",children:"3"}),(0,e.jsx)(n.span,{className:"token punctuation",children:","})," ",(0,e.jsx)(n.span,{className:"token number",children:"5"}),(0,e.jsx)(n.span,{className:"token punctuation",children:","})," ",(0,e.jsx)(n.span,{className:"token number",children:"1"}),(0,e.jsx)(n.span,{className:"token punctuation",children:"]"}),` `]}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"26",children:["heapsort",(0,e.jsx)(n.span,{className:"token punctuation",children:"("}),"arr",(0,e.jsx)(n.span,{className:"token punctuation",children:")"}),` `]}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"27",children:[(0,e.jsx)(n.span,{className:"token keyword",children:"print"}),(0,e.jsx)(n.span,{className:"token punctuation",children:"("}),"arr",(0,e.jsx)(n.span,{className:"token punctuation",children:")"}),` `]})]})})]}),` `,(0,e.jsxs)("details",{className:"code-block",children:[(0,e.jsx)("summary",{children:"JavaScript"}),(0,e.jsx)(n.pre,{className:"language-js",children:(0,e.jsxs)(n.code,{className:"language-js code-highlight",children:[(0,e.jsxs)(n.span,{className:"code-line line-number",line:"1",children:[(0,e.jsx)(n.span,{className:"token keyword",children:"function"})," ",(0,e.jsx)(n.span,{className:"token function",children:"heapify"}),(0,e.jsx)(n.span,{className:"token punctuation",children:"("}),(0,e.jsxs)(n.span,{className:"token parameter",children:["arr",(0,e.jsx)(n.span,{className:"token punctuation",children:","})," n",(0,e.jsx)(n.span,{className:"token punctuation",children:","})," i"]}),(0,e.jsx)(n.span,{className:"token punctuation",children:")"})," ",(0,e.jsx)(n.span,{className:"token punctuation",children:"{"}),` `]}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"2",children:[" ",(0,e.jsx)(n.span,{className:"token keyword",children:"let"})," largest ",(0,e.jsx)(n.span,{className:"token operator",children:"="})," i",(0,e.jsx)(n.span,{className:"token punctuation",children:";"}),` `]}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"3",children:[" ",(0,e.jsx)(n.span,{className:"token keyword",children:"const"})," left ",(0,e.jsx)(n.span,{className:"token operator",children:"="})," ",(0,e.jsx)(n.span,{className:"token number",children:"2"})," ",(0,e.jsx)(n.span,{className:"token operator",children:"*"})," i ",(0,e.jsx)(n.span,{className:"token operator",children:"+"})," ",(0,e.jsx)(n.span,{className:"token number",children:"1"}),(0,e.jsx)(n.span,{className:"token punctuation",children:";"}),` `]}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"4",children:[" ",(0,e.jsx)(n.span,{className:"token keyword",children:"const"})," right ",(0,e.jsx)(n.span,{className:"token operator",children:"="})," ",(0,e.jsx)(n.span,{className:"token number",children:"2"})," ",(0,e.jsx)(n.span,{className:"token operator",children:"*"})," i ",(0,e.jsx)(n.span,{className:"token operator",children:"+"})," ",(0,e.jsx)(n.span,{className:"token number",children:"2"}),(0,e.jsx)(n.span,{className:"token punctuation",children:";"}),` `]}),(0,e.jsx)(n.span,{className:"code-line line-number",line:"5",children:` `}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"6",children:[" ",(0,e.jsx)(n.span,{className:"token keyword control-flow",children:"if"})," ",(0,e.jsx)(n.span,{className:"token punctuation",children:"("}),"left ",(0,e.jsx)(n.span,{className:"token operator",children:"<"})," n ",(0,e.jsx)(n.span,{className:"token operator",children:"&&"})," arr",(0,e.jsx)(n.span,{className:"token punctuation",children:"["}),"i",(0,e.jsx)(n.span,{className:"token punctuation",children:"]"})," ",(0,e.jsx)(n.span,{className:"token operator",children:"<"})," arr",(0,e.jsx)(n.span,{className:"token punctuation",children:"["}),"left",(0,e.jsx)(n.span,{className:"token punctuation",children:"]"}),(0,e.jsx)(n.span,{className:"token punctuation",children:")"})," ",(0,e.jsx)(n.span,{className:"token punctuation",children:"{"}),` `]}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"7",children:[" largest ",(0,e.jsx)(n.span,{className:"token operator",children:"="})," left",(0,e.jsx)(n.span,{className:"token punctuation",children:";"}),` `]}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"8",children:[" ",(0,e.jsx)(n.span,{className:"token punctuation",children:"}"}),` `]}),(0,e.jsx)(n.span,{className:"code-line line-number",line:"9",children:` `}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"10",children:[" ",(0,e.jsx)(n.span,{className:"token keyword control-flow",children:"if"})," ",(0,e.jsx)(n.span,{className:"token punctuation",children:"("}),"right ",(0,e.jsx)(n.span,{className:"token operator",children:"<"})," n ",(0,e.jsx)(n.span,{className:"token operator",children:"&&"})," arr",(0,e.jsx)(n.span,{className:"token punctuation",children:"["}),"largest",(0,e.jsx)(n.span,{className:"token punctuation",children:"]"})," ",(0,e.jsx)(n.span,{className:"token operator",children:"<"})," arr",(0,e.jsx)(n.span,{className:"token punctuation",children:"["}),"right",(0,e.jsx)(n.span,{className:"token punctuation",children:"]"}),(0,e.jsx)(n.span,{className:"token punctuation",children:")"})," ",(0,e.jsx)(n.span,{className:"token punctuation",children:"{"}),` `]}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"11",children:[" largest ",(0,e.jsx)(n.span,{className:"token operator",children:"="})," right",(0,e.jsx)(n.span,{className:"token punctuation",children:";"}),` `]}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"12",children:[" ",(0,e.jsx)(n.span,{className:"token punctuation",children:"}"}),` `]}),(0,e.jsx)(n.span,{className:"code-line line-number",line:"13",children:` `}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"14",children:[" ",(0,e.jsx)(n.span,{className:"token keyword control-flow",children:"if"})," ",(0,e.jsx)(n.span,{className:"token punctuation",children:"("}),"largest ",(0,e.jsx)(n.span,{className:"token operator",children:"!=="})," i",(0,e.jsx)(n.span,{className:"token punctuation",children:")"})," ",(0,e.jsx)(n.span,{className:"token punctuation",children:"{"}),` `]}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"15",children:[" ",(0,e.jsx)(n.span,{className:"token punctuation",children:"["}),"arr",(0,e.jsx)(n.span,{className:"token punctuation",children:"["}),"i",(0,e.jsx)(n.span,{className:"token punctuation",children:"]"}),(0,e.jsx)(n.span,{className:"token punctuation",children:","})," arr",(0,e.jsx)(n.span,{className:"token punctuation",children:"["}),"largest",(0,e.jsx)(n.span,{className:"token punctuation",children:"]"}),(0,e.jsx)(n.span,{className:"token punctuation",children:"]"})," ",(0,e.jsx)(n.span,{className:"token operator",children:"="})," ",(0,e.jsx)(n.span,{className:"token punctuation",children:"["}),"arr",(0,e.jsx)(n.span,{className:"token punctuation",children:"["}),"largest",(0,e.jsx)(n.span,{className:"token punctuation",children:"]"}),(0,e.jsx)(n.span,{className:"token punctuation",children:","})," arr",(0,e.jsx)(n.span,{className:"token punctuation",children:"["}),"i",(0,e.jsx)(n.span,{className:"token punctuation",children:"]"}),(0,e.jsx)(n.span,{className:"token punctuation",children:"]"}),(0,e.jsx)(n.span,{className:"token punctuation",children:";"})," ",(0,e.jsx)(n.span,{className:"token comment",children:"// Swap"}),` `]}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"16",children:[" ",(0,e.jsx)(n.span,{className:"token function",children:"heapify"}),(0,e.jsx)(n.span,{className:"token punctuation",children:"("}),"arr",(0,e.jsx)(n.span,{className:"token punctuation",children:","})," n",(0,e.jsx)(n.span,{className:"token punctuation",children:","})," largest",(0,e.jsx)(n.span,{className:"token punctuation",children:")"}),(0,e.jsx)(n.span,{className:"token punctuation",children:";"}),` `]}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"17",children:[" ",(0,e.jsx)(n.span,{className:"token punctuation",children:"}"}),` `]}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"18",children:[(0,e.jsx)(n.span,{className:"token punctuation",children:"}"}),` `]}),(0,e.jsx)(n.span,{className:"code-line line-number",line:"19",children:` `}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"20",children:[(0,e.jsx)(n.span,{className:"token keyword",children:"function"})," ",(0,e.jsx)(n.span,{className:"token function",children:"heapsort"}),(0,e.jsx)(n.span,{className:"token punctuation",children:"("}),(0,e.jsx)(n.span,{className:"token parameter",children:"arr"}),(0,e.jsx)(n.span,{className:"token punctuation",children:")"})," ",(0,e.jsx)(n.span,{className:"token punctuation",children:"{"}),` `]}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"21",children:[" ",(0,e.jsx)(n.span,{className:"token keyword",children:"const"})," n ",(0,e.jsx)(n.span,{className:"token operator",children:"="})," arr",(0,e.jsx)(n.span,{className:"token punctuation",children:"."}),(0,e.jsx)(n.span,{className:"token property-access",children:"length"}),(0,e.jsx)(n.span,{className:"token punctuation",children:";"}),` `]}),(0,e.jsx)(n.span,{className:"code-line line-number",line:"22",children:` `}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"23",children:[" ",(0,e.jsx)(n.span,{className:"token comment",children:"// Build heap (rearrange array)"}),` `]}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"24",children:[" ",(0,e.jsx)(n.span,{className:"token keyword control-flow",children:"for"})," ",(0,e.jsx)(n.span,{className:"token punctuation",children:"("}),(0,e.jsx)(n.span,{className:"token keyword",children:"let"})," i ",(0,e.jsx)(n.span,{className:"token operator",children:"="})," ",(0,e.jsx)(n.span,{className:"token known-class-name class-name",children:"Math"}),(0,e.jsx)(n.span,{className:"token punctuation",children:"."}),(0,e.jsx)(n.span,{className:"token method function property-access",children:"floor"}),(0,e.jsx)(n.span,{className:"token punctuation",children:"("}),"n ",(0,e.jsx)(n.span,{className:"token operator",children:"/"})," ",(0,e.jsx)(n.span,{className:"token number",children:"2"}),(0,e.jsx)(n.span,{className:"token punctuation",children:")"})," ",(0,e.jsx)(n.span,{className:"token operator",children:"-"})," ",(0,e.jsx)(n.span,{className:"token number",children:"1"}),(0,e.jsx)(n.span,{className:"token punctuation",children:";"})," i ",(0,e.jsx)(n.span,{className:"token operator",children:">="})," ",(0,e.jsx)(n.span,{className:"token number",children:"0"}),(0,e.jsx)(n.span,{className:"token punctuation",children:";"})," i",(0,e.jsx)(n.span,{className:"token operator",children:"--"}),(0,e.jsx)(n.span,{className:"token punctuation",children:")"})," ",(0,e.jsx)(n.span,{className:"token punctuation",children:"{"}),` `]}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"25",children:[" ",(0,e.jsx)(n.span,{className:"token function",children:"heapify"}),(0,e.jsx)(n.span,{className:"token punctuation",children:"("}),"arr",(0,e.jsx)(n.span,{className:"token punctuation",children:","})," n",(0,e.jsx)(n.span,{className:"token punctuation",children:","})," i",(0,e.jsx)(n.span,{className:"token punctuation",children:")"}),(0,e.jsx)(n.span,{className:"token punctuation",children:";"}),` `]}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"26",children:[" ",(0,e.jsx)(n.span,{className:"token punctuation",children:"}"}),` `]}),(0,e.jsx)(n.span,{className:"code-line line-number",line:"27",children:` `}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"28",children:[" ",(0,e.jsx)(n.span,{className:"token comment",children:"// One by one extract an element from heap"}),` `]}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"29",children:[" ",(0,e.jsx)(n.span,{className:"token keyword control-flow",children:"for"})," ",(0,e.jsx)(n.span,{className:"token punctuation",children:"("}),(0,e.jsx)(n.span,{className:"token keyword",children:"let"})," i ",(0,e.jsx)(n.span,{className:"token operator",children:"="})," n ",(0,e.jsx)(n.span,{className:"token operator",children:"-"})," ",(0,e.jsx)(n.span,{className:"token number",children:"1"}),(0,e.jsx)(n.span,{className:"token punctuation",children:";"})," i ",(0,e.jsx)(n.span,{className:"token operator",children:">"})," ",(0,e.jsx)(n.span,{className:"token number",children:"0"}),(0,e.jsx)(n.span,{className:"token punctuation",children:";"})," i",(0,e.jsx)(n.span,{className:"token operator",children:"--"}),(0,e.jsx)(n.span,{className:"token punctuation",children:")"})," ",(0,e.jsx)(n.span,{className:"token punctuation",children:"{"}),` `]}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"30",children:[" ",(0,e.jsx)(n.span,{className:"token punctuation",children:"["}),"arr",(0,e.jsx)(n.span,{className:"token punctuation",children:"["}),(0,e.jsx)(n.span,{className:"token number",children:"0"}),(0,e.jsx)(n.span,{className:"token punctuation",children:"]"}),(0,e.jsx)(n.span,{className:"token punctuation",children:","})," arr",(0,e.jsx)(n.span,{className:"token punctuation",children:"["}),"i",(0,e.jsx)(n.span,{className:"token punctuation",children:"]"}),(0,e.jsx)(n.span,{className:"token punctuation",children:"]"})," ",(0,e.jsx)(n.span,{className:"token operator",children:"="})," ",(0,e.jsx)(n.span,{className:"token punctuation",children:"["}),"arr",(0,e.jsx)(n.span,{className:"token punctuation",children:"["}),"i",(0,e.jsx)(n.span,{className:"token punctuation",children:"]"}),(0,e.jsx)(n.span,{className:"token punctuation",children:","})," arr",(0,e.jsx)(n.span,{className:"token punctuation",children:"["}),(0,e.jsx)(n.span,{className:"token number",children:"0"}),(0,e.jsx)(n.span,{className:"token punctuation",children:"]"}),(0,e.jsx)(n.span,{className:"token punctuation",children:"]"}),(0,e.jsx)(n.span,{className:"token punctuation",children:";"})," ",(0,e.jsx)(n.span,{className:"token comment",children:"// Move current root to end"}),` `]}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"31",children:[" ",(0,e.jsx)(n.span,{className:"token function",children:"heapify"}),(0,e.jsx)(n.span,{className:"token punctuation",children:"("}),"arr",(0,e.jsx)(n.span,{className:"token punctuation",children:","})," i",(0,e.jsx)(n.span,{className:"token punctuation",children:","})," ",(0,e.jsx)(n.span,{className:"token number",children:"0"}),(0,e.jsx)(n.span,{className:"token punctuation",children:")"}),(0,e.jsx)(n.span,{className:"token punctuation",children:";"}),` `]}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"32",children:[" ",(0,e.jsx)(n.span,{className:"token punctuation",children:"}"}),` `]}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"33",children:[(0,e.jsx)(n.span,{className:"token punctuation",children:"}"}),` `]}),(0,e.jsx)(n.span,{className:"code-line line-number",line:"34",children:` `}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"35",children:[(0,e.jsx)(n.span,{className:"token keyword",children:"const"})," arr ",(0,e.jsx)(n.span,{className:"token operator",children:"="})," ",(0,e.jsx)(n.span,{className:"token punctuation",children:"["}),(0,e.jsx)(n.span,{className:"token number",children:"4"}),(0,e.jsx)(n.span,{className:"token punctuation",children:","})," ",(0,e.jsx)(n.span,{className:"token number",children:"10"}),(0,e.jsx)(n.span,{className:"token punctuation",children:","})," ",(0,e.jsx)(n.span,{className:"token number",children:"3"}),(0,e.jsx)(n.span,{className:"token punctuation",children:","})," ",(0,e.jsx)(n.span,{className:"token number",children:"5"}),(0,e.jsx)(n.span,{className:"token punctuation",children:","})," ",(0,e.jsx)(n.span,{className:"token number",children:"1"}),(0,e.jsx)(n.span,{className:"token punctuation",children:"]"}),(0,e.jsx)(n.span,{className:"token punctuation",children:";"}),` `]}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"36",children:[(0,e.jsx)(n.span,{className:"token function",children:"heapsort"}),(0,e.jsx)(n.span,{className:"token punctuation",children:"("}),"arr",(0,e.jsx)(n.span,{className:"token punctuation",children:")"}),(0,e.jsx)(n.span,{className:"token punctuation",children:";"}),` `]}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"37",children:[(0,e.jsx)(n.span,{className:"token console class-name",children:"console"}),(0,e.jsx)(n.span,{className:"token punctuation",children:"."}),(0,e.jsx)(n.span,{className:"token method function property-access",children:"log"}),(0,e.jsx)(n.span,{className:"token punctuation",children:"("}),"arr",(0,e.jsx)(n.span,{className:"token punctuation",children:")"}),(0,e.jsx)(n.span,{className:"token punctuation",children:";"}),` `]})]})})]}),` `,(0,e.jsxs)("details",{className:"code-block",children:[(0,e.jsx)("summary",{children:"Java"}),(0,e.jsx)(n.pre,{className:"language-java",children:(0,e.jsxs)(n.code,{className:"language-java code-highlight",children:[(0,e.jsxs)(n.span,{className:"code-line line-number",line:"1",children:[(0,e.jsx)(n.span,{className:"token keyword",children:"public"})," ",(0,e.jsx)(n.span,{className:"token keyword",children:"class"})," ",(0,e.jsx)(n.span,{className:"token class-name",children:"HeapSort"})," ",(0,e.jsx)(n.span,{className:"token punctuation",children:"{"}),` `]}),(0,e.jsx)(n.span,{className:"code-line line-number",line:"2",children:` `}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"3",children:[" ",(0,e.jsx)(n.span,{className:"token keyword",children:"public"})," ",(0,e.jsx)(n.span,{className:"token keyword",children:"void"})," ",(0,e.jsx)(n.span,{className:"token function",children:"heapify"}),(0,e.jsx)(n.span,{className:"token punctuation",children:"("}),(0,e.jsx)(n.span,{className:"token keyword",children:"int"}),(0,e.jsx)(n.span,{className:"token punctuation",children:"["}),(0,e.jsx)(n.span,{className:"token punctuation",children:"]"})," arr",(0,e.jsx)(n.span,{className:"token punctuation",children:","})," ",(0,e.jsx)(n.span,{className:"token keyword",children:"int"})," n",(0,e.jsx)(n.span,{className:"token punctuation",children:","})," ",(0,e.jsx)(n.span,{className:"token keyword",children:"int"})," i",(0,e.jsx)(n.span,{className:"token punctuation",children:")"})," ",(0,e.jsx)(n.span,{className:"token punctuation",children:"{"}),` `]}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"4",children:[" ",(0,e.jsx)(n.span,{className:"token keyword",children:"int"})," largest ",(0,e.jsx)(n.span,{className:"token operator",children:"="})," i",(0,e.jsx)(n.span,{className:"token punctuation",children:";"}),` `]}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"5",children:[" ",(0,e.jsx)(n.span,{className:"token keyword",children:"int"})," left ",(0,e.jsx)(n.span,{className:"token operator",children:"="})," ",(0,e.jsx)(n.span,{className:"token number",children:"2"})," ",(0,e.jsx)(n.span,{className:"token operator",children:"*"})," i ",(0,e.jsx)(n.span,{className:"token operator",children:"+"})," ",(0,e.jsx)(n.span,{className:"token number",children:"1"}),(0,e.jsx)(n.span,{className:"token punctuation",children:";"}),` `]}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"6",children:[" ",(0,e.jsx)(n.span,{className:"token keyword",children:"int"})," right ",(0,e.jsx)(n.span,{className:"token operator",children:"="})," ",(0,e.jsx)(n.span,{className:"token number",children:"2"})," ",(0,e.jsx)(n.span,{className:"token operator",children:"*"})," i ",(0,e.jsx)(n.span,{className:"token operator",children:"+"})," ",(0,e.jsx)(n.span,{className:"token number",children:"2"}),(0,e.jsx)(n.span,{className:"token punctuation",children:";"}),` `]}),(0,e.jsx)(n.span,{className:"code-line line-number",line:"7",children:` `}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"8",children:[" ",(0,e.jsx)(n.span,{className:"token keyword",children:"if"})," ",(0,e.jsx)(n.span,{className:"token punctuation",children:"("}),"left ",(0,e.jsx)(n.span,{className:"token operator",children:"<"})," n ",(0,e.jsx)(n.span,{className:"token operator",children:"&&"})," arr",(0,e.jsx)(n.span,{className:"token punctuation",children:"["}),"i",(0,e.jsx)(n.span,{className:"token punctuation",children:"]"})," ",(0,e.jsx)(n.span,{className:"token operator",children:"<"})," arr",(0,e.jsx)(n.span,{className:"token punctuation",children:"["}),"left",(0,e.jsx)(n.span,{className:"token punctuation",children:"]"}),(0,e.jsx)(n.span,{className:"token punctuation",children:")"})," ",(0,e.jsx)(n.span,{className:"token punctuation",children:"{"}),` `]}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"9",children:[" largest ",(0,e.jsx)(n.span,{className:"token operator",children:"="})," left",(0,e.jsx)(n.span,{className:"token punctuation",children:";"}),` `]}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"10",children:[" ",(0,e.jsx)(n.span,{className:"token punctuation",children:"}"}),` `]}),(0,e.jsx)(n.span,{className:"code-line line-number",line:"11",children:` `}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"12",children:[" ",(0,e.jsx)(n.span,{className:"token keyword",children:"if"})," ",(0,e.jsx)(n.span,{className:"token punctuation",children:"("}),"right ",(0,e.jsx)(n.span,{className:"token operator",children:"<"})," n ",(0,e.jsx)(n.span,{className:"token operator",children:"&&"})," arr",(0,e.jsx)(n.span,{className:"token punctuation",children:"["}),"largest",(0,e.jsx)(n.span,{className:"token punctuation",children:"]"})," ",(0,e.jsx)(n.span,{className:"token operator",children:"<"})," arr",(0,e.jsx)(n.span,{className:"token punctuation",children:"["}),"right",(0,e.jsx)(n.span,{className:"token punctuation",children:"]"}),(0,e.jsx)(n.span,{className:"token punctuation",children:")"})," ",(0,e.jsx)(n.span,{className:"token punctuation",children:"{"}),` `]}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"13",children:[" largest ",(0,e.jsx)(n.span,{className:"token operator",children:"="})," right",(0,e.jsx)(n.span,{className:"token punctuation",children:";"}),` `]}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"14",children:[" ",(0,e.jsx)(n.span,{className:"token punctuation",children:"}"}),` `]}),(0,e.jsx)(n.span,{className:"code-line line-number",line:"15",children:` `}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"16",children:[" ",(0,e.jsx)(n.span,{className:"token keyword",children:"if"})," ",(0,e.jsx)(n.span,{className:"token punctuation",children:"("}),"largest ",(0,e.jsx)(n.span,{className:"token operator",children:"!="})," i",(0,e.jsx)(n.span,{className:"token punctuation",children:")"})," ",(0,e.jsx)(n.span,{className:"token punctuation",children:"{"}),` `]}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"17",children:[" ",(0,e.jsx)(n.span,{className:"token keyword",children:"int"})," swap ",(0,e.jsx)(n.span,{className:"token operator",children:"="})," arr",(0,e.jsx)(n.span,{className:"token punctuation",children:"["}),"i",(0,e.jsx)(n.span,{className:"token punctuation",children:"]"}),(0,e.jsx)(n.span,{className:"token punctuation",children:";"}),` `]}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"18",children:[" arr",(0,e.jsx)(n.span,{className:"token punctuation",children:"["}),"i",(0,e.jsx)(n.span,{className:"token punctuation",children:"]"})," ",(0,e.jsx)(n.span,{className:"token operator",children:"="})," arr",(0,e.jsx)(n.span,{className:"token punctuation",children:"["}),"largest",(0,e.jsx)(n.span,{className:"token punctuation",children:"]"}),(0,e.jsx)(n.span,{className:"token punctuation",children:";"}),` `]}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"19",children:[" arr",(0,e.jsx)(n.span,{className:"token punctuation",children:"["}),"largest",(0,e.jsx)(n.span,{className:"token punctuation",children:"]"})," ",(0,e.jsx)(n.span,{className:"token operator",children:"="})," swap",(0,e.jsx)(n.span,{className:"token punctuation",children:";"}),` `]}),(0,e.jsx)(n.span,{className:"code-line line-number",line:"20",children:` `}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"21",children:[" ",(0,e.jsx)(n.span,{className:"token function",children:"heapify"}),(0,e.jsx)(n.span,{className:"token punctuation",children:"("}),"arr",(0,e.jsx)(n.span,{className:"token punctuation",children:","})," n",(0,e.jsx)(n.span,{className:"token punctuation",children:","})," largest",(0,e.jsx)(n.span,{className:"token punctuation",children:")"}),(0,e.jsx)(n.span,{className:"token punctuation",children:";"}),` `]}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"22",children:[" ",(0,e.jsx)(n.span,{className:"token punctuation",children:"}"}),` `]}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"23",children:[" ",(0,e.jsx)(n.span,{className:"token punctuation",children:"}"}),` `]}),(0,e.jsx)(n.span,{className:"code-line line-number",line:"24",children:` `}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"25",children:[" ",(0,e.jsx)(n.span,{className:"token keyword",children:"public"})," ",(0,e.jsx)(n.span,{className:"token keyword",children:"void"})," ",(0,e.jsx)(n.span,{className:"token function",children:"heapsort"}),(0,e.jsx)(n.span,{className:"token punctuation",children:"("}),(0,e.jsx)(n.span,{className:"token keyword",children:"int"}),(0,e.jsx)(n.span,{className:"token punctuation",children:"["}),(0,e.jsx)(n.span,{className:"token punctuation",children:"]"})," arr",(0,e.jsx)(n.span,{className:"token punctuation",children:")"})," ",(0,e.jsx)(n.span,{className:"token punctuation",children:"{"}),` `]}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"26",children:[" ",(0,e.jsx)(n.span,{className:"token keyword",children:"int"})," n ",(0,e.jsx)(n.span,{className:"token operator",children:"="})," arr",(0,e.jsx)(n.span,{className:"token punctuation",children:"."}),"length",(0,e.jsx)(n.span,{className:"token punctuation",children:";"}),` `]}),(0,e.jsx)(n.span,{className:"code-line line-number",line:"27",children:` `}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"28",children:[" ",(0,e.jsx)(n.span,{className:"token comment",children:"// Build heap (rearrange array)"}),` `]}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"29",children:[" ",(0,e.jsx)(n.span,{className:"token keyword",children:"for"})," ",(0,e.jsx)(n.span,{className:"token punctuation",children:"("}),(0,e.jsx)(n.span,{className:"token keyword",children:"int"})," i ",(0,e.jsx)(n.span,{className:"token operator",children:"="})," n ",(0,e.jsx)(n.span,{className:"token operator",children:"/"})," ",(0,e.jsx)(n.span,{className:"token number",children:"2"})," ",(0,e.jsx)(n.span,{className:"token operator",children:"-"})," ",(0,e.jsx)(n.span,{className:"token number",children:"1"}),(0,e.jsx)(n.span,{className:"token punctuation",children:";"})," i ",(0,e.jsx)(n.span,{className:"token operator",children:">="})," ",(0,e.jsx)(n.span,{className:"token number",children:"0"}),(0,e.jsx)(n.span,{className:"token punctuation",children:";"})," i",(0,e.jsx)(n.span,{className:"token operator",children:"--"}),(0,e.jsx)(n.span,{className:"token punctuation",children:")"})," ",(0,e.jsx)(n.span,{className:"token punctuation",children:"{"}),` `]}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"30",children:[" ",(0,e.jsx)(n.span,{className:"token function",children:"heapify"}),(0,e.jsx)(n.span,{className:"token punctuation",children:"("}),"arr",(0,e.jsx)(n.span,{className:"token punctuation",children:","})," n",(0,e.jsx)(n.span,{className:"token punctuation",children:","})," i",(0,e.jsx)(n.span,{className:"token punctuation",children:")"}),(0,e.jsx)(n.span,{className:"token punctuation",children:";"}),` `]}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"31",children:[" ",(0,e.jsx)(n.span,{className:"token punctuation",children:"}"}),` `]}),(0,e.jsx)(n.span,{className:"code-line line-number",line:"32",children:` `}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"33",children:[" ",(0,e.jsx)(n.span,{className:"token comment",children:"// One by one extract an element from heap"}),` `]}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"34",children:[" ",(0,e.jsx)(n.span,{className:"token keyword",children:"for"})," ",(0,e.jsx)(n.span,{className:"token punctuation",children:"("}),(0,e.jsx)(n.span,{className:"token keyword",children:"int"})," i ",(0,e.jsx)(n.span,{className:"token operator",children:"="})," n ",(0,e.jsx)(n.span,{className:"token operator",children:"-"})," ",(0,e.jsx)(n.span,{className:"token number",children:"1"}),(0,e.jsx)(n.span,{className:"token punctuation",children:";"})," i ",(0,e.jsx)(n.span,{className:"token operator",children:">"})," ",(0,e.jsx)(n.span,{className:"token number",children:"0"}),(0,e.jsx)(n.span,{className:"token punctuation",children:";"})," i",(0,e.jsx)(n.span,{className:"token operator",children:"--"}),(0,e.jsx)(n.span,{className:"token punctuation",children:")"})," ",(0,e.jsx)(n.span,{className:"token punctuation",children:"{"}),` `]}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"35",children:[" ",(0,e.jsx)(n.span,{className:"token keyword",children:"int"})," temp ",(0,e.jsx)(n.span,{className:"token operator",children:"="})," arr",(0,e.jsx)(n.span,{className:"token punctuation",children:"["}),(0,e.jsx)(n.span,{className:"token number",children:"0"}),(0,e.jsx)(n.span,{className:"token punctuation",children:"]"}),(0,e.jsx)(n.span,{className:"token punctuation",children:";"}),` `]}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"36",children:[" arr",(0,e.jsx)(n.span,{className:"token punctuation",children:"["}),(0,e.jsx)(n.span,{className:"token number",children:"0"}),(0,e.jsx)(n.span,{className:"token punctuation",children:"]"})," ",(0,e.jsx)(n.span,{className:"token operator",children:"="})," arr",(0,e.jsx)(n.span,{className:"token punctuation",children:"["}),"i",(0,e.jsx)(n.span,{className:"token punctuation",children:"]"}),(0,e.jsx)(n.span,{className:"token punctuation",children:";"}),` `]}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"37",children:[" arr",(0,e.jsx)(n.span,{className:"token punctuation",children:"["}),"i",(0,e.jsx)(n.span,{className:"token punctuation",children:"]"})," ",(0,e.jsx)(n.span,{className:"token operator",children:"="})," temp",(0,e.jsx)(n.span,{className:"token punctuation",children:";"}),` `]}),(0,e.jsx)(n.span,{className:"code-line line-number",line:"38",children:` `}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"39",children:[" ",(0,e.jsx)(n.span,{className:"token function",children:"heapify"}),(0,e.jsx)(n.span,{className:"token punctuation",children:"("}),"arr",(0,e.jsx)(n.span,{className:"token punctuation",children:","})," i",(0,e.jsx)(n.span,{className:"token punctuation",children:","})," ",(0,e.jsx)(n.span,{className:"token number",children:"0"}),(0,e.jsx)(n.span,{className:"token punctuation",children:")"}),(0,e.jsx)(n.span,{className:"token punctuation",children:";"}),` `]}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"40",children:[" ",(0,e.jsx)(n.span,{className:"token punctuation",children:"}"}),` `]}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"41",children:[" ",(0,e.jsx)(n.span,{className:"token punctuation",children:"}"}),` `]}),(0,e.jsx)(n.span,{className:"code-line line-number",line:"42",children:` `}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"43",children:[" ",(0,e.jsx)(n.span,{className:"token keyword",children:"public"})," ",(0,e.jsx)(n.span,{className:"token keyword",children:"static"})," ",(0,e.jsx)(n.span,{className:"token keyword",children:"void"})," ",(0,e.jsx)(n.span,{className:"token function",children:"main"}),(0,e.jsx)(n.span,{className:"token punctuation",children:"("}),(0,e.jsx)(n.span,{className:"token class-name",children:"String"}),(0,e.jsx)(n.span,{className:"token punctuation",children:"["}),(0,e.jsx)(n.span,{className:"token punctuation",children:"]"})," args",(0,e.jsx)(n.span,{className:"token punctuation",children:")"})," ",(0,e.jsx)(n.span,{className:"token punctuation",children:"{"}),` `]}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"44",children:[" ",(0,e.jsx)(n.span,{className:"token keyword",children:"int"}),(0,e.jsx)(n.span,{className:"token punctuation",children:"["}),(0,e.jsx)(n.span,{className:"token punctuation",children:"]"})," arr ",(0,e.jsx)(n.span,{className:"token operator",children:"="})," ",(0,e.jsx)(n.span,{className:"token punctuation",children:"{"}),(0,e.jsx)(n.span,{className:"token number",children:"4"}),(0,e.jsx)(n.span,{className:"token punctuation",children:","})," ",(0,e.jsx)(n.span,{className:"token number",children:"10"}),(0,e.jsx)(n.span,{className:"token punctuation",children:","})," ",(0,e.jsx)(n.span,{className:"token number",children:"3"}),(0,e.jsx)(n.span,{className:"token punctuation",children:","})," ",(0,e.jsx)(n.span,{className:"token number",children:"5"}),(0,e.jsx)(n.span,{className:"token punctuation",children:","})," ",(0,e.jsx)(n.span,{className:"token number",children:"1"}),(0,e.jsx)(n.span,{className:"token punctuation",children:"}"}),(0,e.jsx)(n.span,{className:"token punctuation",children:";"}),` `]}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"45",children:[" ",(0,e.jsx)(n.span,{className:"token class-name",children:"HeapSort"})," sorter ",(0,e.jsx)(n.span,{className:"token operator",children:"="})," ",(0,e.jsx)(n.span,{className:"token keyword",children:"new"})," ",(0,e.jsx)(n.span,{className:"token class-name",children:"HeapSort"}),(0,e.jsx)(n.span,{className:"token punctuation",children:"("}),(0,e.jsx)(n.span,{className:"token punctuation",children:")"}),(0,e.jsx)(n.span,{className:"token punctuation",children:";"}),` `]}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"46",children:[" sorter",(0,e.jsx)(n.span,{className:"token punctuation",children:"."}),(0,e.jsx)(n.span,{className:"token function",children:"heapsort"}),(0,e.jsx)(n.span,{className:"token punctuation",children:"("}),"arr",(0,e.jsx)(n.span,{className:"token punctuation",children:")"}),(0,e.jsx)(n.span,{className:"token punctuation",children:";"}),` `]}),(0,e.jsx)(n.span,{className:"code-line line-number",line:"47",children:` `}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"48",children:[" ",(0,e.jsx)(n.span,{className:"token keyword",children:"for"})," ",(0,e.jsx)(n.span,{className:"token punctuation",children:"("}),(0,e.jsx)(n.span,{className:"token keyword",children:"int"})," num ",(0,e.jsx)(n.span,{className:"token operator",children:":"})," arr",(0,e.jsx)(n.span,{className:"token punctuation",children:")"})," ",(0,e.jsx)(n.span,{className:"token punctuation",children:"{"}),` `]}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"49",children:[" ",(0,e.jsx)(n.span,{className:"token class-name",children:"System"}),(0,e.jsx)(n.span,{className:"token punctuation",children:"."}),"out",(0,e.jsx)(n.span,{className:"token punctuation",children:"."}),(0,e.jsx)(n.span,{className:"token function",children:"print"}),(0,e.jsx)(n.span,{className:"token punctuation",children:"("}),"num ",(0,e.jsx)(n.span,{className:"token operator",children:"+"})," ",(0,e.jsx)(n.span,{className:"token string",children:'" "'}),(0,e.jsx)(n.span,{className:"token punctuation",children:")"}),(0,e.jsx)(n.span,{className:"token punctuation",children:";"}),` `]}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"50",children:[" ",(0,e.jsx)(n.span,{className:"token punctuation",children:"}"}),` `]}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"51",children:[" ",(0,e.jsx)(n.span,{className:"token punctuation",children:"}"}),` `]}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"52",children:[(0,e.jsx)(n.span,{className:"token punctuation",children:"}"}),` `]})]})})]}),` `,(0,e.jsxs)("details",{className:"code-block",children:[(0,e.jsx)("summary",{children:"C++"}),(0,e.jsx)(n.pre,{className:"language-cpp",children:(0,e.jsxs)(n.code,{className:"language-cpp code-highlight",children:[(0,e.jsxs)(n.span,{className:"code-line line-number",line:"1",children:[(0,e.jsxs)(n.span,{className:"token macro property",children:[(0,e.jsx)(n.span,{className:"token directive-hash",children:"#"}),(0,e.jsx)(n.span,{className:"token directive keyword",children:"include"})," ",(0,e.jsx)(n.span,{className:"token string",children:""})]}),` `]}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"2",children:[(0,e.jsxs)(n.span,{className:"token macro property",children:[(0,e.jsx)(n.span,{className:"token directive-hash",children:"#"}),(0,e.jsx)(n.span,{className:"token directive keyword",children:"include"})," ",(0,e.jsx)(n.span,{className:"token string",children:""})]}),` `]}),(0,e.jsx)(n.span,{className:"code-line line-number",line:"3",children:` `}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"4",children:[(0,e.jsx)(n.span,{className:"token keyword",children:"using"})," ",(0,e.jsx)(n.span,{className:"token keyword",children:"namespace"})," std",(0,e.jsx)(n.span,{className:"token punctuation",children:";"}),` `]}),(0,e.jsx)(n.span,{className:"code-line line-number",line:"5",children:` `}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"6",children:[(0,e.jsx)(n.span,{className:"token keyword",children:"void"})," ",(0,e.jsx)(n.span,{className:"token function",children:"heapify"}),(0,e.jsx)(n.span,{className:"token punctuation",children:"("}),"vector",(0,e.jsx)(n.span,{className:"token operator",children:"<"}),(0,e.jsx)(n.span,{className:"token keyword",children:"int"}),(0,e.jsx)(n.span,{className:"token operator",children:">"}),(0,e.jsx)(n.span,{className:"token operator",children:"&"})," arr",(0,e.jsx)(n.span,{className:"token punctuation",children:","})," ",(0,e.jsx)(n.span,{className:"token keyword",children:"int"})," n",(0,e.jsx)(n.span,{className:"token punctuation",children:","})," ",(0,e.jsx)(n.span,{className:"token keyword",children:"int"})," i",(0,e.jsx)(n.span,{className:"token punctuation",children:")"})," ",(0,e.jsx)(n.span,{className:"token punctuation",children:"{"}),` `]}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"7",children:[" ",(0,e.jsx)(n.span,{className:"token keyword",children:"int"})," largest ",(0,e.jsx)(n.span,{className:"token operator",children:"="})," i",(0,e.jsx)(n.span,{className:"token punctuation",children:";"})," ",(0,e.jsx)(n.span,{className:"token comment",children:"// Initialize largest as root"}),` `]}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"8",children:[" ",(0,e.jsx)(n.span,{className:"token keyword",children:"int"})," left ",(0,e.jsx)(n.span,{className:"token operator",children:"="})," ",(0,e.jsx)(n.span,{className:"token number",children:"2"})," ",(0,e.jsx)(n.span,{className:"token operator",children:"*"})," i ",(0,e.jsx)(n.span,{className:"token operator",children:"+"})," ",(0,e.jsx)(n.span,{className:"token number",children:"1"}),(0,e.jsx)(n.span,{className:"token punctuation",children:";"})," ",(0,e.jsx)(n.span,{className:"token comment",children:"// left = 2*i + 1"}),` `]}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"9",children:[" ",(0,e.jsx)(n.span,{className:"token keyword",children:"int"})," right ",(0,e.jsx)(n.span,{className:"token operator",children:"="})," ",(0,e.jsx)(n.span,{className:"token number",children:"2"})," ",(0,e.jsx)(n.span,{className:"token operator",children:"*"})," i ",(0,e.jsx)(n.span,{className:"token operator",children:"+"})," ",(0,e.jsx)(n.span,{className:"token number",children:"2"}),(0,e.jsx)(n.span,{className:"token punctuation",children:";"})," ",(0,e.jsx)(n.span,{className:"token comment",children:"// right = 2*i + 2"}),` `]}),(0,e.jsx)(n.span,{className:"code-line line-number",line:"10",children:` `}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"11",children:[" ",(0,e.jsx)(n.span,{className:"token comment",children:"// If left child is larger than root"}),` `]}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"12",children:[" ",(0,e.jsx)(n.span,{className:"token keyword",children:"if"})," ",(0,e.jsx)(n.span,{className:"token punctuation",children:"("}),"left ",(0,e.jsx)(n.span,{className:"token operator",children:"<"})," n ",(0,e.jsx)(n.span,{className:"token operator",children:"&&"})," arr",(0,e.jsx)(n.span,{className:"token punctuation",children:"["}),"left",(0,e.jsx)(n.span,{className:"token punctuation",children:"]"})," ",(0,e.jsx)(n.span,{className:"token operator",children:">"})," arr",(0,e.jsx)(n.span,{className:"token punctuation",children:"["}),"largest",(0,e.jsx)(n.span,{className:"token punctuation",children:"]"}),(0,e.jsx)(n.span,{className:"token punctuation",children:")"}),` `]}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"13",children:[" largest ",(0,e.jsx)(n.span,{className:"token operator",children:"="})," left",(0,e.jsx)(n.span,{className:"token punctuation",children:";"}),` `]}),(0,e.jsx)(n.span,{className:"code-line line-number",line:"14",children:` `}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"15",children:[" ",(0,e.jsx)(n.span,{className:"token comment",children:"// If right child is larger than largest so far"}),` `]}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"16",children:[" ",(0,e.jsx)(n.span,{className:"token keyword",children:"if"})," ",(0,e.jsx)(n.span,{className:"token punctuation",children:"("}),"right ",(0,e.jsx)(n.span,{className:"token operator",children:"<"})," n ",(0,e.jsx)(n.span,{className:"token operator",children:"&&"})," arr",(0,e.jsx)(n.span,{className:"token punctuation",children:"["}),"right",(0,e.jsx)(n.span,{className:"token punctuation",children:"]"})," ",(0,e.jsx)(n.span,{className:"token operator",children:">"})," arr",(0,e.jsx)(n.span,{className:"token punctuation",children:"["}),"largest",(0,e.jsx)(n.span,{className:"token punctuation",children:"]"}),(0,e.jsx)(n.span,{className:"token punctuation",children:")"}),` `]}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"17",children:[" largest ",(0,e.jsx)(n.span,{className:"token operator",children:"="})," right",(0,e.jsx)(n.span,{className:"token punctuation",children:";"}),` `]}),(0,e.jsx)(n.span,{className:"code-line line-number",line:"18",children:` `}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"19",children:[" ",(0,e.jsx)(n.span,{className:"token comment",children:"// If largest is not root"}),` `]}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"20",children:[" ",(0,e.jsx)(n.span,{className:"token keyword",children:"if"})," ",(0,e.jsx)(n.span,{className:"token punctuation",children:"("}),"largest ",(0,e.jsx)(n.span,{className:"token operator",children:"!="})," i",(0,e.jsx)(n.span,{className:"token punctuation",children:")"})," ",(0,e.jsx)(n.span,{className:"token punctuation",children:"{"}),` `]}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"21",children:[" ",(0,e.jsx)(n.span,{className:"token function",children:"swap"}),(0,e.jsx)(n.span,{className:"token punctuation",children:"("}),"arr",(0,e.jsx)(n.span,{className:"token punctuation",children:"["}),"i",(0,e.jsx)(n.span,{className:"token punctuation",children:"]"}),(0,e.jsx)(n.span,{className:"token punctuation",children:","})," arr",(0,e.jsx)(n.span,{className:"token punctuation",children:"["}),"largest",(0,e.jsx)(n.span,{className:"token punctuation",children:"]"}),(0,e.jsx)(n.span,{className:"token punctuation",children:")"}),(0,e.jsx)(n.span,{className:"token punctuation",children:";"}),` `]}),(0,e.jsx)(n.span,{className:"code-line line-number",line:"22",children:` `}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"23",children:[" ",(0,e.jsx)(n.span,{className:"token comment",children:"// Recursively heapify the affected sub-tree"}),` `]}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"24",children:[" ",(0,e.jsx)(n.span,{className:"token function",children:"heapify"}),(0,e.jsx)(n.span,{className:"token punctuation",children:"("}),"arr",(0,e.jsx)(n.span,{className:"token punctuation",children:","})," n",(0,e.jsx)(n.span,{className:"token punctuation",children:","})," largest",(0,e.jsx)(n.span,{className:"token punctuation",children:")"}),(0,e.jsx)(n.span,{className:"token punctuation",children:";"}),` `]}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"25",children:[" ",(0,e.jsx)(n.span,{className:"token punctuation",children:"}"}),` `]}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"26",children:[(0,e.jsx)(n.span,{className:"token punctuation",children:"}"}),` `]}),(0,e.jsx)(n.span,{className:"code-line line-number",line:"27",children:` `}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"28",children:[(0,e.jsx)(n.span,{className:"token keyword",children:"void"})," ",(0,e.jsx)(n.span,{className:"token function",children:"heapsort"}),(0,e.jsx)(n.span,{className:"token punctuation",children:"("}),"vector",(0,e.jsx)(n.span,{className:"token operator",children:"<"}),(0,e.jsx)(n.span,{className:"token keyword",children:"int"}),(0,e.jsx)(n.span,{className:"token operator",children:">"}),(0,e.jsx)(n.span,{className:"token operator",children:"&"})," arr",(0,e.jsx)(n.span,{className:"token punctuation",children:")"})," ",(0,e.jsx)(n.span,{className:"token punctuation",children:"{"}),` `]}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"29",children:[" ",(0,e.jsx)(n.span,{className:"token keyword",children:"int"})," n ",(0,e.jsx)(n.span,{className:"token operator",children:"="})," arr",(0,e.jsx)(n.span,{className:"token punctuation",children:"."}),(0,e.jsx)(n.span,{className:"token function",children:"size"}),(0,e.jsx)(n.span,{className:"token punctuation",children:"("}),(0,e.jsx)(n.span,{className:"token punctuation",children:")"}),(0,e.jsx)(n.span,{className:"token punctuation",children:";"}),` `]}),(0,e.jsx)(n.span,{className:"code-line line-number",line:"30",children:` `}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"31",children:[" ",(0,e.jsx)(n.span,{className:"token comment",children:"// Build heap (rearrange array)"}),` `]}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"32",children:[" ",(0,e.jsx)(n.span,{className:"token keyword",children:"for"})," ",(0,e.jsx)(n.span,{className:"token punctuation",children:"("}),(0,e.jsx)(n.span,{className:"token keyword",children:"int"})," i ",(0,e.jsx)(n.span,{className:"token operator",children:"="})," n ",(0,e.jsx)(n.span,{className:"token operator",children:"/"})," ",(0,e.jsx)(n.span,{className:"token number",children:"2"})," ",(0,e.jsx)(n.span,{className:"token operator",children:"-"})," ",(0,e.jsx)(n.span,{className:"token number",children:"1"}),(0,e.jsx)(n.span,{className:"token punctuation",children:";"})," i ",(0,e.jsx)(n.span,{className:"token operator",children:">="})," ",(0,e.jsx)(n.span,{className:"token number",children:"0"}),(0,e.jsx)(n.span,{className:"token punctuation",children:";"})," i",(0,e.jsx)(n.span,{className:"token operator",children:"--"}),(0,e.jsx)(n.span,{className:"token punctuation",children:")"}),` `]}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"33",children:[" ",(0,e.jsx)(n.span,{className:"token function",children:"heapify"}),(0,e.jsx)(n.span,{className:"token punctuation",children:"("}),"arr",(0,e.jsx)(n.span,{className:"token punctuation",children:","})," n",(0,e.jsx)(n.span,{className:"token punctuation",children:","})," i",(0,e.jsx)(n.span,{className:"token punctuation",children:")"}),(0,e.jsx)(n.span,{className:"token punctuation",children:";"}),` `]}),(0,e.jsx)(n.span,{className:"code-line line-number",line:"34",children:` `}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"35",children:[" ",(0,e.jsx)(n.span,{className:"token comment",children:"// One by one extract an element from heap"}),` `]}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"36",children:[" ",(0,e.jsx)(n.span,{className:"token keyword",children:"for"})," ",(0,e.jsx)(n.span,{className:"token punctuation",children:"("}),(0,e.jsx)(n.span,{className:"token keyword",children:"int"})," i ",(0,e.jsx)(n.span,{className:"token operator",children:"="})," n ",(0,e.jsx)(n.span,{className:"token operator",children:"-"})," ",(0,e.jsx)(n.span,{className:"token number",children:"1"}),(0,e.jsx)(n.span,{className:"token punctuation",children:";"})," i ",(0,e.jsx)(n.span,{className:"token operator",children:">"})," ",(0,e.jsx)(n.span,{className:"token number",children:"0"}),(0,e.jsx)(n.span,{className:"token punctuation",children:";"})," i",(0,e.jsx)(n.span,{className:"token operator",children:"--"}),(0,e.jsx)(n.span,{className:"token punctuation",children:")"})," ",(0,e.jsx)(n.span,{className:"token punctuation",children:"{"}),` `]}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"37",children:[" ",(0,e.jsx)(n.span,{className:"token comment",children:"// Move current root to end"}),` `]}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"38",children:[" ",(0,e.jsx)(n.span,{className:"token function",children:"swap"}),(0,e.jsx)(n.span,{className:"token punctuation",children:"("}),"arr",(0,e.jsx)(n.span,{className:"token punctuation",children:"["}),(0,e.jsx)(n.span,{className:"token number",children:"0"}),(0,e.jsx)(n.span,{className:"token punctuation",children:"]"}),(0,e.jsx)(n.span,{className:"token punctuation",children:","})," arr",(0,e.jsx)(n.span,{className:"token punctuation",children:"["}),"i",(0,e.jsx)(n.span,{className:"token punctuation",children:"]"}),(0,e.jsx)(n.span,{className:"token punctuation",children:")"}),(0,e.jsx)(n.span,{className:"token punctuation",children:";"}),` `]}),(0,e.jsx)(n.span,{className:"code-line line-number",line:"39",children:` `}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"40",children:[" ",(0,e.jsx)(n.span,{className:"token comment",children:"// Call max heapify on the reduced heap"}),` `]}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"41",children:[" ",(0,e.jsx)(n.span,{className:"token function",children:"heapify"}),(0,e.jsx)(n.span,{className:"token punctuation",children:"("}),"arr",(0,e.jsx)(n.span,{className:"token punctuation",children:","})," i",(0,e.jsx)(n.span,{className:"token punctuation",children:","})," ",(0,e.jsx)(n.span,{className:"token number",children:"0"}),(0,e.jsx)(n.span,{className:"token punctuation",children:")"}),(0,e.jsx)(n.span,{className:"token punctuation",children:";"}),` `]}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"42",children:[" ",(0,e.jsx)(n.span,{className:"token punctuation",children:"}"}),` `]}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"43",children:[(0,e.jsx)(n.span,{className:"token punctuation",children:"}"}),` `]}),(0,e.jsx)(n.span,{className:"code-line line-number",line:"44",children:` `}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"45",children:[(0,e.jsx)(n.span,{className:"token keyword",children:"int"})," ",(0,e.jsx)(n.span,{className:"token function",children:"main"}),(0,e.jsx)(n.span,{className:"token punctuation",children:"("}),(0,e.jsx)(n.span,{className:"token punctuation",children:")"})," ",(0,e.jsx)(n.span,{className:"token punctuation",children:"{"}),` `]}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"46",children:[" vector",(0,e.jsx)(n.span,{className:"token operator",children:"<"}),(0,e.jsx)(n.span,{className:"token keyword",children:"int"}),(0,e.jsx)(n.span,{className:"token operator",children:">"})," arr ",(0,e.jsx)(n.span,{className:"token operator",children:"="})," ",(0,e.jsx)(n.span,{className:"token punctuation",children:"{"}),(0,e.jsx)(n.span,{className:"token number",children:"4"}),(0,e.jsx)(n.span,{className:"token punctuation",children:","})," ",(0,e.jsx)(n.span,{className:"token number",children:"10"}),(0,e.jsx)(n.span,{className:"token punctuation",children:","})," ",(0,e.jsx)(n.span,{className:"token number",children:"3"}),(0,e.jsx)(n.span,{className:"token punctuation",children:","})," ",(0,e.jsx)(n.span,{className:"token number",children:"5"}),(0,e.jsx)(n.span,{className:"token punctuation",children:","})," ",(0,e.jsx)(n.span,{className:"token number",children:"1"}),(0,e.jsx)(n.span,{className:"token punctuation",children:"}"}),(0,e.jsx)(n.span,{className:"token punctuation",children:";"}),` `]}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"47",children:[" ",(0,e.jsx)(n.span,{className:"token function",children:"heapsort"}),(0,e.jsx)(n.span,{className:"token punctuation",children:"("}),"arr",(0,e.jsx)(n.span,{className:"token punctuation",children:")"}),(0,e.jsx)(n.span,{className:"token punctuation",children:";"}),` `]}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"48",children:[" ",(0,e.jsx)(n.span,{className:"token keyword",children:"for"})," ",(0,e.jsx)(n.span,{className:"token punctuation",children:"("}),(0,e.jsx)(n.span,{className:"token keyword",children:"int"})," i ",(0,e.jsx)(n.span,{className:"token operator",children:"="})," ",(0,e.jsx)(n.span,{className:"token number",children:"0"}),(0,e.jsx)(n.span,{className:"token punctuation",children:";"})," i ",(0,e.jsx)(n.span,{className:"token operator",children:"<"})," arr",(0,e.jsx)(n.span,{className:"token punctuation",children:"."}),(0,e.jsx)(n.span,{className:"token function",children:"size"}),(0,e.jsx)(n.span,{className:"token punctuation",children:"("}),(0,e.jsx)(n.span,{className:"token punctuation",children:")"}),(0,e.jsx)(n.span,{className:"token punctuation",children:";"})," i",(0,e.jsx)(n.span,{className:"token operator",children:"++"}),(0,e.jsx)(n.span,{className:"token punctuation",children:")"}),` `]}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"49",children:[" cout ",(0,e.jsx)(n.span,{className:"token operator",children:"<<"})," arr",(0,e.jsx)(n.span,{className:"token punctuation",children:"["}),"i",(0,e.jsx)(n.span,{className:"token punctuation",children:"]"})," ",(0,e.jsx)(n.span,{className:"token operator",children:"<<"})," ",(0,e.jsx)(n.span,{className:"token string",children:'" "'}),(0,e.jsx)(n.span,{className:"token punctuation",children:";"}),` `]}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"50",children:[" cout ",(0,e.jsx)(n.span,{className:"token operator",children:"<<"})," endl",(0,e.jsx)(n.span,{className:"token punctuation",children:";"}),` `]}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"51",children:[" ",(0,e.jsx)(n.span,{className:"token keyword",children:"return"})," ",(0,e.jsx)(n.span,{className:"token number",children:"0"}),(0,e.jsx)(n.span,{className:"token punctuation",children:";"}),` `]}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"52",children:[(0,e.jsx)(n.span,{className:"token punctuation",children:"}"}),` `]})]})})]}),` `,(0,e.jsxs)("details",{className:"code-block",children:[(0,e.jsx)("summary",{children:"Go"}),(0,e.jsx)(n.pre,{className:"language-go",children:(0,e.jsxs)(n.code,{className:"language-go code-highlight",children:[(0,e.jsxs)(n.span,{className:"code-line line-number",line:"1",children:[(0,e.jsx)(n.span,{className:"token keyword",children:"package"}),` main `]}),(0,e.jsx)(n.span,{className:"code-line line-number",line:"2",children:` `}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"3",children:[(0,e.jsx)(n.span,{className:"token keyword",children:"import"})," ",(0,e.jsx)(n.span,{className:"token string",children:'"fmt"'}),` `]}),(0,e.jsx)(n.span,{className:"code-line line-number",line:"4",children:` `}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"5",children:[(0,e.jsx)(n.span,{className:"token keyword",children:"func"})," ",(0,e.jsx)(n.span,{className:"token function",children:"heapify"}),(0,e.jsx)(n.span,{className:"token punctuation",children:"("}),"arr ",(0,e.jsx)(n.span,{className:"token punctuation",children:"["}),(0,e.jsx)(n.span,{className:"token punctuation",children:"]"}),(0,e.jsx)(n.span,{className:"token builtin",children:"int"}),(0,e.jsx)(n.span,{className:"token punctuation",children:","})," n",(0,e.jsx)(n.span,{className:"token punctuation",children:","})," i ",(0,e.jsx)(n.span,{className:"token builtin",children:"int"}),(0,e.jsx)(n.span,{className:"token punctuation",children:")"})," ",(0,e.jsx)(n.span,{className:"token punctuation",children:"{"}),` `]}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"6",children:[" largest ",(0,e.jsx)(n.span,{className:"token operator",children:":="}),` i `]}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"7",children:[" left ",(0,e.jsx)(n.span,{className:"token operator",children:":="})," ",(0,e.jsx)(n.span,{className:"token number",children:"2"}),(0,e.jsx)(n.span,{className:"token operator",children:"*"}),"i ",(0,e.jsx)(n.span,{className:"token operator",children:"+"})," ",(0,e.jsx)(n.span,{className:"token number",children:"1"}),` `]}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"8",children:[" right ",(0,e.jsx)(n.span,{className:"token operator",children:":="})," ",(0,e.jsx)(n.span,{className:"token number",children:"2"}),(0,e.jsx)(n.span,{className:"token operator",children:"*"}),"i ",(0,e.jsx)(n.span,{className:"token operator",children:"+"})," ",(0,e.jsx)(n.span,{className:"token number",children:"2"}),` `]}),(0,e.jsx)(n.span,{className:"code-line line-number",line:"9",children:` `}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"10",children:[" ",(0,e.jsx)(n.span,{className:"token keyword",children:"if"})," left ",(0,e.jsx)(n.span,{className:"token operator",children:"<"})," n ",(0,e.jsx)(n.span,{className:"token operator",children:"&&"})," arr",(0,e.jsx)(n.span,{className:"token punctuation",children:"["}),"i",(0,e.jsx)(n.span,{className:"token punctuation",children:"]"})," ",(0,e.jsx)(n.span,{className:"token operator",children:"<"})," arr",(0,e.jsx)(n.span,{className:"token punctuation",children:"["}),"left",(0,e.jsx)(n.span,{className:"token punctuation",children:"]"})," ",(0,e.jsx)(n.span,{className:"token punctuation",children:"{"}),` `]}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"11",children:[" largest ",(0,e.jsx)(n.span,{className:"token operator",children:"="}),` left `]}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"12",children:[" ",(0,e.jsx)(n.span,{className:"token punctuation",children:"}"}),` `]}),(0,e.jsx)(n.span,{className:"code-line line-number",line:"13",children:` `}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"14",children:[" ",(0,e.jsx)(n.span,{className:"token keyword",children:"if"})," right ",(0,e.jsx)(n.span,{className:"token operator",children:"<"})," n ",(0,e.jsx)(n.span,{className:"token operator",children:"&&"})," arr",(0,e.jsx)(n.span,{className:"token punctuation",children:"["}),"largest",(0,e.jsx)(n.span,{className:"token punctuation",children:"]"})," ",(0,e.jsx)(n.span,{className:"token operator",children:"<"})," arr",(0,e.jsx)(n.span,{className:"token punctuation",children:"["}),"right",(0,e.jsx)(n.span,{className:"token punctuation",children:"]"})," ",(0,e.jsx)(n.span,{className:"token punctuation",children:"{"}),` `]}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"15",children:[" largest ",(0,e.jsx)(n.span,{className:"token operator",children:"="}),` right `]}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"16",children:[" ",(0,e.jsx)(n.span,{className:"token punctuation",children:"}"}),` `]}),(0,e.jsx)(n.span,{className:"code-line line-number",line:"17",children:` `}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"18",children:[" ",(0,e.jsx)(n.span,{className:"token keyword",children:"if"})," largest ",(0,e.jsx)(n.span,{className:"token operator",children:"!="})," i ",(0,e.jsx)(n.span,{className:"token punctuation",children:"{"}),` `]}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"19",children:[" arr",(0,e.jsx)(n.span,{className:"token punctuation",children:"["}),"i",(0,e.jsx)(n.span,{className:"token punctuation",children:"]"}),(0,e.jsx)(n.span,{className:"token punctuation",children:","})," arr",(0,e.jsx)(n.span,{className:"token punctuation",children:"["}),"largest",(0,e.jsx)(n.span,{className:"token punctuation",children:"]"})," ",(0,e.jsx)(n.span,{className:"token operator",children:"="})," arr",(0,e.jsx)(n.span,{className:"token punctuation",children:"["}),"largest",(0,e.jsx)(n.span,{className:"token punctuation",children:"]"}),(0,e.jsx)(n.span,{className:"token punctuation",children:","})," arr",(0,e.jsx)(n.span,{className:"token punctuation",children:"["}),"i",(0,e.jsx)(n.span,{className:"token punctuation",children:"]"}),` `]}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"20",children:[" ",(0,e.jsx)(n.span,{className:"token function",children:"heapify"}),(0,e.jsx)(n.span,{className:"token punctuation",children:"("}),"arr",(0,e.jsx)(n.span,{className:"token punctuation",children:","})," n",(0,e.jsx)(n.span,{className:"token punctuation",children:","})," largest",(0,e.jsx)(n.span,{className:"token punctuation",children:")"}),` `]}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"21",children:[" ",(0,e.jsx)(n.span,{className:"token punctuation",children:"}"}),` `]}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"22",children:[(0,e.jsx)(n.span,{className:"token punctuation",children:"}"}),` `]}),(0,e.jsx)(n.span,{className:"code-line line-number",line:"23",children:` `}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"24",children:[(0,e.jsx)(n.span,{className:"token keyword",children:"func"})," ",(0,e.jsx)(n.span,{className:"token function",children:"heapsort"}),(0,e.jsx)(n.span,{className:"token punctuation",children:"("}),"arr ",(0,e.jsx)(n.span,{className:"token punctuation",children:"["}),(0,e.jsx)(n.span,{className:"token punctuation",children:"]"}),(0,e.jsx)(n.span,{className:"token builtin",children:"int"}),(0,e.jsx)(n.span,{className:"token punctuation",children:")"})," ",(0,e.jsx)(n.span,{className:"token punctuation",children:"{"}),` `]}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"25",children:[" n ",(0,e.jsx)(n.span,{className:"token operator",children:":="})," ",(0,e.jsx)(n.span,{className:"token function",children:"len"}),(0,e.jsx)(n.span,{className:"token punctuation",children:"("}),"arr",(0,e.jsx)(n.span,{className:"token punctuation",children:")"}),` `]}),(0,e.jsx)(n.span,{className:"code-line line-number",line:"26",children:` `}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"27",children:[" ",(0,e.jsx)(n.span,{className:"token comment",children:"// Build heap (rearrange array)"}),` `]}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"28",children:[" ",(0,e.jsx)(n.span,{className:"token keyword",children:"for"})," i ",(0,e.jsx)(n.span,{className:"token operator",children:":="})," n",(0,e.jsx)(n.span,{className:"token operator",children:"/"}),(0,e.jsx)(n.span,{className:"token number",children:"2"})," ",(0,e.jsx)(n.span,{className:"token operator",children:"-"})," ",(0,e.jsx)(n.span,{className:"token number",children:"1"}),(0,e.jsx)(n.span,{className:"token punctuation",children:";"})," i ",(0,e.jsx)(n.span,{className:"token operator",children:">="})," ",(0,e.jsx)(n.span,{className:"token number",children:"0"}),(0,e.jsx)(n.span,{className:"token punctuation",children:";"})," i",(0,e.jsx)(n.span,{className:"token operator",children:"--"})," ",(0,e.jsx)(n.span,{className:"token punctuation",children:"{"}),` `]}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"29",children:[" ",(0,e.jsx)(n.span,{className:"token function",children:"heapify"}),(0,e.jsx)(n.span,{className:"token punctuation",children:"("}),"arr",(0,e.jsx)(n.span,{className:"token punctuation",children:","})," n",(0,e.jsx)(n.span,{className:"token punctuation",children:","})," i",(0,e.jsx)(n.span,{className:"token punctuation",children:")"}),` `]}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"30",children:[" ",(0,e.jsx)(n.span,{className:"token punctuation",children:"}"}),` `]}),(0,e.jsx)(n.span,{className:"code-line line-number",line:"31",children:` `}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"32",children:[" ",(0,e.jsx)(n.span,{className:"token comment",children:"// One by one extract an element from heap"}),` `]}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"33",children:[" ",(0,e.jsx)(n.span,{className:"token keyword",children:"for"})," i ",(0,e.jsx)(n.span,{className:"token operator",children:":="})," n ",(0,e.jsx)(n.span,{className:"token operator",children:"-"})," ",(0,e.jsx)(n.span,{className:"token number",children:"1"}),(0,e.jsx)(n.span,{className:"token punctuation",children:";"})," i ",(0,e.jsx)(n.span,{className:"token operator",children:">"})," ",(0,e.jsx)(n.span,{className:"token number",children:"0"}),(0,e.jsx)(n.span,{className:"token punctuation",children:";"})," i",(0,e.jsx)(n.span,{className:"token operator",children:"--"})," ",(0,e.jsx)(n.span,{className:"token punctuation",children:"{"}),` `]}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"34",children:[" arr",(0,e.jsx)(n.span,{className:"token punctuation",children:"["}),(0,e.jsx)(n.span,{className:"token number",children:"0"}),(0,e.jsx)(n.span,{className:"token punctuation",children:"]"}),(0,e.jsx)(n.span,{className:"token punctuation",children:","})," arr",(0,e.jsx)(n.span,{className:"token punctuation",children:"["}),"i",(0,e.jsx)(n.span,{className:"token punctuation",children:"]"})," ",(0,e.jsx)(n.span,{className:"token operator",children:"="})," arr",(0,e.jsx)(n.span,{className:"token punctuation",children:"["}),"i",(0,e.jsx)(n.span,{className:"token punctuation",children:"]"}),(0,e.jsx)(n.span,{className:"token punctuation",children:","})," arr",(0,e.jsx)(n.span,{className:"token punctuation",children:"["}),(0,e.jsx)(n.span,{className:"token number",children:"0"}),(0,e.jsx)(n.span,{className:"token punctuation",children:"]"}),` `]}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"35",children:[" ",(0,e.jsx)(n.span,{className:"token function",children:"heapify"}),(0,e.jsx)(n.span,{className:"token punctuation",children:"("}),"arr",(0,e.jsx)(n.span,{className:"token punctuation",children:","})," i",(0,e.jsx)(n.span,{className:"token punctuation",children:","})," ",(0,e.jsx)(n.span,{className:"token number",children:"0"}),(0,e.jsx)(n.span,{className:"token punctuation",children:")"}),` `]}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"36",children:[" ",(0,e.jsx)(n.span,{className:"token punctuation",children:"}"}),` `]}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"37",children:[(0,e.jsx)(n.span,{className:"token punctuation",children:"}"}),` `]}),(0,e.jsx)(n.span,{className:"code-line line-number",line:"38",children:` `}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"39",children:[(0,e.jsx)(n.span,{className:"token keyword",children:"func"})," ",(0,e.jsx)(n.span,{className:"token function",children:"main"}),(0,e.jsx)(n.span,{className:"token punctuation",children:"("}),(0,e.jsx)(n.span,{className:"token punctuation",children:")"})," ",(0,e.jsx)(n.span,{className:"token punctuation",children:"{"}),` `]}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"40",children:[" arr ",(0,e.jsx)(n.span,{className:"token operator",children:":="})," ",(0,e.jsx)(n.span,{className:"token punctuation",children:"["}),(0,e.jsx)(n.span,{className:"token punctuation",children:"]"}),(0,e.jsx)(n.span,{className:"token builtin",children:"int"}),(0,e.jsx)(n.span,{className:"token punctuation",children:"{"}),(0,e.jsx)(n.span,{className:"token number",children:"4"}),(0,e.jsx)(n.span,{className:"token punctuation",children:","})," ",(0,e.jsx)(n.span,{className:"token number",children:"10"}),(0,e.jsx)(n.span,{className:"token punctuation",children:","})," ",(0,e.jsx)(n.span,{className:"token number",children:"3"}),(0,e.jsx)(n.span,{className:"token punctuation",children:","})," ",(0,e.jsx)(n.span,{className:"token number",children:"5"}),(0,e.jsx)(n.span,{className:"token punctuation",children:","})," ",(0,e.jsx)(n.span,{className:"token number",children:"1"}),(0,e.jsx)(n.span,{className:"token punctuation",children:"}"}),` `]}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"41",children:[" ",(0,e.jsx)(n.span,{className:"token function",children:"heapsort"}),(0,e.jsx)(n.span,{className:"token punctuation",children:"("}),"arr",(0,e.jsx)(n.span,{className:"token punctuation",children:")"}),` `]}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"42",children:[" fmt",(0,e.jsx)(n.span,{className:"token punctuation",children:"."}),(0,e.jsx)(n.span,{className:"token function",children:"Println"}),(0,e.jsx)(n.span,{className:"token punctuation",children:"("}),"arr",(0,e.jsx)(n.span,{className:"token punctuation",children:")"}),` `]}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"43",children:[(0,e.jsx)(n.span,{className:"token punctuation",children:"}"}),` `]})]})})]}),` `,(0,e.jsxs)("details",{className:"code-block",children:[(0,e.jsx)("summary",{children:"Rust"}),(0,e.jsx)(n.pre,{className:"language-rust",children:(0,e.jsxs)(n.code,{className:"language-rust code-highlight",children:[(0,e.jsxs)(n.span,{className:"code-line line-number",line:"1",children:[(0,e.jsx)(n.span,{className:"token keyword",children:"fn"})," ",(0,e.jsx)(n.span,{className:"token function-definition function",children:"heapify"}),(0,e.jsx)(n.span,{className:"token punctuation",children:"("}),"arr",(0,e.jsx)(n.span,{className:"token punctuation",children:":"})," ",(0,e.jsx)(n.span,{className:"token operator",children:"&"}),(0,e.jsx)(n.span,{className:"token keyword",children:"mut"})," ",(0,e.jsx)(n.span,{className:"token punctuation",children:"["}),(0,e.jsx)(n.span,{className:"token keyword",children:"i32"}),(0,e.jsx)(n.span,{className:"token punctuation",children:"]"}),(0,e.jsx)(n.span,{className:"token punctuation",children:","})," n",(0,e.jsx)(n.span,{className:"token punctuation",children:":"})," ",(0,e.jsx)(n.span,{className:"token keyword",children:"usize"}),(0,e.jsx)(n.span,{className:"token punctuation",children:","})," i",(0,e.jsx)(n.span,{className:"token punctuation",children:":"})," ",(0,e.jsx)(n.span,{className:"token keyword",children:"usize"}),(0,e.jsx)(n.span,{className:"token punctuation",children:")"})," ",(0,e.jsx)(n.span,{className:"token punctuation",children:"{"}),` `]}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"2",children:[" ",(0,e.jsx)(n.span,{className:"token keyword",children:"let"})," ",(0,e.jsx)(n.span,{className:"token keyword",children:"mut"})," largest ",(0,e.jsx)(n.span,{className:"token operator",children:"="})," i",(0,e.jsx)(n.span,{className:"token punctuation",children:";"}),` `]}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"3",children:[" ",(0,e.jsx)(n.span,{className:"token keyword",children:"let"})," left ",(0,e.jsx)(n.span,{className:"token operator",children:"="})," ",(0,e.jsx)(n.span,{className:"token number",children:"2"})," ",(0,e.jsx)(n.span,{className:"token operator",children:"*"})," i ",(0,e.jsx)(n.span,{className:"token operator",children:"+"})," ",(0,e.jsx)(n.span,{className:"token number",children:"1"}),(0,e.jsx)(n.span,{className:"token punctuation",children:";"}),` `]}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"4",children:[" ",(0,e.jsx)(n.span,{className:"token keyword",children:"let"})," right ",(0,e.jsx)(n.span,{className:"token operator",children:"="})," ",(0,e.jsx)(n.span,{className:"token number",children:"2"})," ",(0,e.jsx)(n.span,{className:"token operator",children:"*"})," i ",(0,e.jsx)(n.span,{className:"token operator",children:"+"})," ",(0,e.jsx)(n.span,{className:"token number",children:"2"}),(0,e.jsx)(n.span,{className:"token punctuation",children:";"}),` `]}),(0,e.jsx)(n.span,{className:"code-line line-number",line:"5",children:` `}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"6",children:[" ",(0,e.jsx)(n.span,{className:"token keyword",children:"if"})," left ",(0,e.jsx)(n.span,{className:"token operator",children:"<"})," n ",(0,e.jsx)(n.span,{className:"token operator",children:"&&"})," arr",(0,e.jsx)(n.span,{className:"token punctuation",children:"["}),"left",(0,e.jsx)(n.span,{className:"token punctuation",children:"]"})," ",(0,e.jsx)(n.span,{className:"token operator",children:">"})," arr",(0,e.jsx)(n.span,{className:"token punctuation",children:"["}),"largest",(0,e.jsx)(n.span,{className:"token punctuation",children:"]"})," ",(0,e.jsx)(n.span,{className:"token punctuation",children:"{"}),` `]}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"7",children:[" largest ",(0,e.jsx)(n.span,{className:"token operator",children:"="})," left",(0,e.jsx)(n.span,{className:"token punctuation",children:";"}),` `]}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"8",children:[" ",(0,e.jsx)(n.span,{className:"token punctuation",children:"}"}),` `]}),(0,e.jsx)(n.span,{className:"code-line line-number",line:"9",children:` `}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"10",children:[" ",(0,e.jsx)(n.span,{className:"token keyword",children:"if"})," right ",(0,e.jsx)(n.span,{className:"token operator",children:"<"})," n ",(0,e.jsx)(n.span,{className:"token operator",children:"&&"})," arr",(0,e.jsx)(n.span,{className:"token punctuation",children:"["}),"right",(0,e.jsx)(n.span,{className:"token punctuation",children:"]"})," ",(0,e.jsx)(n.span,{className:"token operator",children:">"})," arr",(0,e.jsx)(n.span,{className:"token punctuation",children:"["}),"largest",(0,e.jsx)(n.span,{className:"token punctuation",children:"]"})," ",(0,e.jsx)(n.span,{className:"token punctuation",children:"{"}),` `]}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"11",children:[" largest ",(0,e.jsx)(n.span,{className:"token operator",children:"="})," right",(0,e.jsx)(n.span,{className:"token punctuation",children:";"}),` `]}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"12",children:[" ",(0,e.jsx)(n.span,{className:"token punctuation",children:"}"}),` `]}),(0,e.jsx)(n.span,{className:"code-line line-number",line:"13",children:` `}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"14",children:[" ",(0,e.jsx)(n.span,{className:"token keyword",children:"if"})," largest ",(0,e.jsx)(n.span,{className:"token operator",children:"!="})," i ",(0,e.jsx)(n.span,{className:"token punctuation",children:"{"}),` `]}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"15",children:[" arr",(0,e.jsx)(n.span,{className:"token punctuation",children:"."}),(0,e.jsx)(n.span,{className:"token function",children:"swap"}),(0,e.jsx)(n.span,{className:"token punctuation",children:"("}),"i",(0,e.jsx)(n.span,{className:"token punctuation",children:","})," largest",(0,e.jsx)(n.span,{className:"token punctuation",children:")"}),(0,e.jsx)(n.span,{className:"token punctuation",children:";"}),` `]}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"16",children:[" ",(0,e.jsx)(n.span,{className:"token function",children:"heapify"}),(0,e.jsx)(n.span,{className:"token punctuation",children:"("}),"arr",(0,e.jsx)(n.span,{className:"token punctuation",children:","})," n",(0,e.jsx)(n.span,{className:"token punctuation",children:","})," largest",(0,e.jsx)(n.span,{className:"token punctuation",children:")"}),(0,e.jsx)(n.span,{className:"token punctuation",children:";"}),` `]}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"17",children:[" ",(0,e.jsx)(n.span,{className:"token punctuation",children:"}"}),` `]}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"18",children:[(0,e.jsx)(n.span,{className:"token punctuation",children:"}"}),` `]}),(0,e.jsx)(n.span,{className:"code-line line-number",line:"19",children:` `}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"20",children:[(0,e.jsx)(n.span,{className:"token keyword",children:"fn"})," ",(0,e.jsx)(n.span,{className:"token function-definition function",children:"heapsort"}),(0,e.jsx)(n.span,{className:"token punctuation",children:"("}),"arr",(0,e.jsx)(n.span,{className:"token punctuation",children:":"})," ",(0,e.jsx)(n.span,{className:"token operator",children:"&"}),(0,e.jsx)(n.span,{className:"token keyword",children:"mut"})," ",(0,e.jsx)(n.span,{className:"token punctuation",children:"["}),(0,e.jsx)(n.span,{className:"token keyword",children:"i32"}),(0,e.jsx)(n.span,{className:"token punctuation",children:"]"}),(0,e.jsx)(n.span,{className:"token punctuation",children:")"})," ",(0,e.jsx)(n.span,{className:"token punctuation",children:"{"}),` `]}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"21",children:[" ",(0,e.jsx)(n.span,{className:"token keyword",children:"let"})," n ",(0,e.jsx)(n.span,{className:"token operator",children:"="})," arr",(0,e.jsx)(n.span,{className:"token punctuation",children:"."}),(0,e.jsx)(n.span,{className:"token function",children:"len"}),(0,e.jsx)(n.span,{className:"token punctuation",children:"("}),(0,e.jsx)(n.span,{className:"token punctuation",children:")"}),(0,e.jsx)(n.span,{className:"token punctuation",children:";"}),` `]}),(0,e.jsx)(n.span,{className:"code-line line-number",line:"22",children:` `}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"23",children:[" ",(0,e.jsx)(n.span,{className:"token comment",children:"// Build heap (rearrange array)"}),` `]}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"24",children:[" ",(0,e.jsx)(n.span,{className:"token keyword",children:"for"})," i ",(0,e.jsx)(n.span,{className:"token keyword",children:"in"})," ",(0,e.jsx)(n.span,{className:"token punctuation",children:"("}),(0,e.jsx)(n.span,{className:"token number",children:"0"}),(0,e.jsx)(n.span,{className:"token punctuation",children:".."}),"n ",(0,e.jsx)(n.span,{className:"token operator",children:"/"})," ",(0,e.jsx)(n.span,{className:"token number",children:"2"}),(0,e.jsx)(n.span,{className:"token punctuation",children:")"}),(0,e.jsx)(n.span,{className:"token punctuation",children:"."}),(0,e.jsx)(n.span,{className:"token function",children:"rev"}),(0,e.jsx)(n.span,{className:"token punctuation",children:"("}),(0,e.jsx)(n.span,{className:"token punctuation",children:")"})," ",(0,e.jsx)(n.span,{className:"token punctuation",children:"{"}),` `]}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"25",children:[" ",(0,e.jsx)(n.span,{className:"token function",children:"heapify"}),(0,e.jsx)(n.span,{className:"token punctuation",children:"("}),"arr",(0,e.jsx)(n.span,{className:"token punctuation",children:","})," n",(0,e.jsx)(n.span,{className:"token punctuation",children:","})," i",(0,e.jsx)(n.span,{className:"token punctuation",children:")"}),(0,e.jsx)(n.span,{className:"token punctuation",children:";"}),` `]}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"26",children:[" ",(0,e.jsx)(n.span,{className:"token punctuation",children:"}"}),` `]}),(0,e.jsx)(n.span,{className:"code-line line-number",line:"27",children:` `}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"28",children:[" ",(0,e.jsx)(n.span,{className:"token comment",children:"// One by one extract an element from heap"}),` `]}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"29",children:[" ",(0,e.jsx)(n.span,{className:"token keyword",children:"for"})," i ",(0,e.jsx)(n.span,{className:"token keyword",children:"in"})," ",(0,e.jsx)(n.span,{className:"token punctuation",children:"("}),(0,e.jsx)(n.span,{className:"token number",children:"1"}),(0,e.jsx)(n.span,{className:"token punctuation",children:".."}),"n",(0,e.jsx)(n.span,{className:"token punctuation",children:")"}),(0,e.jsx)(n.span,{className:"token punctuation",children:"."}),(0,e.jsx)(n.span,{className:"token function",children:"rev"}),(0,e.jsx)(n.span,{className:"token punctuation",children:"("}),(0,e.jsx)(n.span,{className:"token punctuation",children:")"})," ",(0,e.jsx)(n.span,{className:"token punctuation",children:"{"}),` `]}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"30",children:[" arr",(0,e.jsx)(n.span,{className:"token punctuation",children:"."}),(0,e.jsx)(n.span,{className:"token function",children:"swap"}),(0,e.jsx)(n.span,{className:"token punctuation",children:"("}),(0,e.jsx)(n.span,{className:"token number",children:"0"}),(0,e.jsx)(n.span,{className:"token punctuation",children:","})," i",(0,e.jsx)(n.span,{className:"token punctuation",children:")"}),(0,e.jsx)(n.span,{className:"token punctuation",children:";"}),` `]}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"31",children:[" ",(0,e.jsx)(n.span,{className:"token function",children:"heapify"}),(0,e.jsx)(n.span,{className:"token punctuation",children:"("}),"arr",(0,e.jsx)(n.span,{className:"token punctuation",children:","})," i",(0,e.jsx)(n.span,{className:"token punctuation",children:","})," ",(0,e.jsx)(n.span,{className:"token number",children:"0"}),(0,e.jsx)(n.span,{className:"token punctuation",children:")"}),(0,e.jsx)(n.span,{className:"token punctuation",children:";"}),` `]}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"32",children:[" ",(0,e.jsx)(n.span,{className:"token punctuation",children:"}"}),` `]}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"33",children:[(0,e.jsx)(n.span,{className:"token punctuation",children:"}"}),` `]}),(0,e.jsx)(n.span,{className:"code-line line-number",line:"34",children:` `}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"35",children:[(0,e.jsx)(n.span,{className:"token keyword",children:"fn"})," ",(0,e.jsx)(n.span,{className:"token function-definition function",children:"main"}),(0,e.jsx)(n.span,{className:"token punctuation",children:"("}),(0,e.jsx)(n.span,{className:"token punctuation",children:")"})," ",(0,e.jsx)(n.span,{className:"token punctuation",children:"{"}),` `]}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"36",children:[" ",(0,e.jsx)(n.span,{className:"token keyword",children:"let"})," ",(0,e.jsx)(n.span,{className:"token keyword",children:"mut"})," arr ",(0,e.jsx)(n.span,{className:"token operator",children:"="})," ",(0,e.jsx)(n.span,{className:"token punctuation",children:"["}),(0,e.jsx)(n.span,{className:"token number",children:"4"}),(0,e.jsx)(n.span,{className:"token punctuation",children:","})," ",(0,e.jsx)(n.span,{className:"token number",children:"10"}),(0,e.jsx)(n.span,{className:"token punctuation",children:","})," ",(0,e.jsx)(n.span,{className:"token number",children:"3"}),(0,e.jsx)(n.span,{className:"token punctuation",children:","})," ",(0,e.jsx)(n.span,{className:"token number",children:"5"}),(0,e.jsx)(n.span,{className:"token punctuation",children:","})," ",(0,e.jsx)(n.span,{className:"token number",children:"1"}),(0,e.jsx)(n.span,{className:"token punctuation",children:"]"}),(0,e.jsx)(n.span,{className:"token punctuation",children:";"}),` `]}),(0,e.jsx)(n.span,{className:"code-line line-number",line:"37",children:` `}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"38",children:[" ",(0,e.jsx)(n.span,{className:"token function",children:"heapsort"}),(0,e.jsx)(n.span,{className:"token punctuation",children:"("}),(0,e.jsx)(n.span,{className:"token operator",children:"&"}),(0,e.jsx)(n.span,{className:"token keyword",children:"mut"})," arr",(0,e.jsx)(n.span,{className:"token punctuation",children:")"}),(0,e.jsx)(n.span,{className:"token punctuation",children:";"}),` `]}),(0,e.jsx)(n.span,{className:"code-line line-number",line:"39",children:` `}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"40",children:[" ",(0,e.jsx)(n.span,{className:"token macro property",children:"println!"}),(0,e.jsx)(n.span,{className:"token punctuation",children:"("}),(0,e.jsx)(n.span,{className:"token string",children:'"Sorted array is: {:?}"'}),(0,e.jsx)(n.span,{className:"token punctuation",children:","})," arr",(0,e.jsx)(n.span,{className:"token punctuation",children:")"}),(0,e.jsx)(n.span,{className:"token punctuation",children:";"}),` `]}),(0,e.jsxs)(n.span,{className:"code-line line-number",line:"41",children:[(0,e.jsx)(n.span,{className:"token punctuation",children:"}"}),` `]})]})})]}),` `,(0,e.jsx)(n.p,{children:(0,e.jsx)(n.strong,{children:"Output"})}),` `,(0,e.jsx)(n.pre,{children:(0,e.jsx)(n.code,{className:"code-highlight",children:(0,e.jsx)(n.span,{className:"code-line",children:`[1, 3, 4, 5, 10] `})})}),` `,(0,e.jsx)(n.h2,{children:"Heapsort Time Complexity"}),` `,(0,e.jsx)(n.p,{children:"Heapsort has a time complexity of O(n log n) for the following reasons:"}),` `,(0,e.jsxs)(n.ul,{children:[` `,(0,e.jsxs)(n.li,{children:[(0,e.jsx)(n.strong,{children:"Heap Building"}),": The initial heap construction takes O(n) time."]}),` `,(0,e.jsxs)(n.li,{children:[(0,e.jsx)(n.strong,{children:"Heapify Operation"}),": After extracting the root, reheapification (heapify) takes O(log n) time. Since we do this for n elements, the sorting phase takes O(n log n)."]}),` `]})]})}function w(a={}){let{wrapper:n}=a.components||{};return n?(0,e.jsx)(n,Object.assign({},a,{children:(0,e.jsx)(p,a)})):p(a)}var x=w;return f(v);})(); ;return Component;

Tag: heapsort

Heap sort