7.4: TODO
- Page ID
- 49313
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)
Merge-heap: it would take two max/min heap and merge them and return a single heap. O(n) time. Make-heap: it would also be nice to describe the O(n) make-heap operation Heap sort: the structure can actually be used to efficiently sort arrays
Make-heap would make use a function heapify
//Element is a data structure// Make-heap(Element Arr[],int size) { for(j=size/2;j>0;j--) { Heapify(Arr,size,j); } }
Heapify(Element Arr[],int size,int t) { L=2*t; R=2*t+1; if(L<size ) { mix=minindex(Arr,L,t); if(R<=size) mix=minindex(Arr,R,mix); } else mix=t; if(mix!=t) { swap(mix,t); Heapify(Arr,size,mix); } }
minindex returns index of the smaller element