Skip to main content
Computer Science

Return to Answer

added 13 characters in body
Source Link
ErroR
ErroR
  • 2k
  • 5
  • 22

Consider the following increasing sorted sequence with size $k=4$ $$ \langle 1,2,3,4 \rangle$$ $1^{th}$ largest element is $4$, and $2^{th}$ largest element is $3$, and $k^{th}$ (i.e. $4^{th}$) largest element is $1$. So for your question, $n^{th}$ largest element for a min-heap $\mathcal{H}$ of size $n$ is equal to $1^{th}$ smallest element in $\mathcal{H}$, because of $\mathcal{H}$ is min-heap, additionally by definition of min-heap, smallest element appear in root of $\mathcal{H}$ , otherwise it contradict with property of min-heap, because it's provable that $k^{th}$ smallest element in $\mathcal{H}$ can go down at most $k$ levels.

Note that, we can conclude that $k^{th}$ ( $k\leq n$) largest element of a min-heap with size $n$ equal to $n-(k-1)$ smallest element.

Consider the following increasing sorted sequence with size $k=4$ $$ \langle 1,2,3,4 \rangle$$ $1^{th}$ largest element is $4$, and $2^{th}$ largest element is $3$, and $k^{th}$ (i.e. $4^{th}$) largest element is $1$. So for your question, $n^{th}$ largest element for a min-heap $\mathcal{H}$ of size $n$ is equal to $1^{th}$ smallest element in $\mathcal{H}$, because of $\mathcal{H}$ is min-heap, additionally by definition of min-heap, smallest element appear in root of $\mathcal{H}$ , otherwise it contradict with property of min-heap, because it's provable that $k^{th}$ smallest element in $\mathcal{H}$ can go down at most $k$ levels.

Note that, we can conclude that $k^{th}$ largest element of a min-heap with size $n$ equal to $n-(k-1)$ smallest element.

Consider the following increasing sorted sequence with size $k=4$ $$ \langle 1,2,3,4 \rangle$$ $1^{th}$ largest element is $4$, and $2^{th}$ largest element is $3$, and $k^{th}$ (i.e. $4^{th}$) largest element is $1$. So for your question, $n^{th}$ largest element for a min-heap $\mathcal{H}$ of size $n$ is equal to $1^{th}$ smallest element in $\mathcal{H}$, because of $\mathcal{H}$ is min-heap, additionally by definition of min-heap, smallest element appear in root of $\mathcal{H}$ , otherwise it contradict with property of min-heap, because it's provable that $k^{th}$ smallest element in $\mathcal{H}$ can go down at most $k$ levels.

Note that, we can conclude that $k^{th}$ ( $k\leq n$) largest element of a min-heap with size $n$ equal to $n-(k-1)$ smallest element.

added 19 characters in body
Source Link
ErroR
ErroR
  • 2k
  • 5
  • 22

Consider the following increasing sorted sequence with size $k=4$ $$ \langle 1,2,3,4 \rangle$$ $1^{th}$ largest element is $4$, and $2^{th}$ largest element is $3$, and $k^{th}$ (i.e. $4^{th}$) largest element is $1$. So for your question, $n^{th}$ largest element for a min-heap $\mathcal{H}$ of size $n$ is equal to $1^{th}$ smallest element in $\mathcal{H}$, because of $\mathcal{H}$ is min-heap, additionally by definition of min-heap, smallest element appear in root of $\mathcal{H}$ , otherwise it contradict with property of min-heap, because it's provable that $k^{th}$ smallest element in $\mathcal{H}$ can go down at most $k$ level. We can conclude that $k^{th}$ largest element of a min-heap with size $n$ equal to $n-(k-1)$ smallest elementlevels.

Note that, we can conclude that $k^{th}$ largest element of a min-heap with size $n$ equal to $n-(k-1)$ smallest element.

Consider the following increasing sorted sequence with size $k=4$ $$ \langle 1,2,3,4 \rangle$$ $1^{th}$ largest element is $4$, and $2^{th}$ largest element is $3$, and $k^{th}$ (i.e. $4^{th}$) largest element is $1$. So for your question, $n^{th}$ largest element for a min-heap $\mathcal{H}$ of size $n$ is equal to $1^{th}$ smallest element in $\mathcal{H}$, because of $\mathcal{H}$ is min-heap, additionally by definition of min-heap, smallest element appear in root of $\mathcal{H}$ , otherwise it contradict with property of min-heap, because it's provable that $k^{th}$ smallest element in $\mathcal{H}$ can go down at most $k$ level. We can conclude that $k^{th}$ largest element of a min-heap with size $n$ equal to $n-(k-1)$ smallest element.

Consider the following increasing sorted sequence with size $k=4$ $$ \langle 1,2,3,4 \rangle$$ $1^{th}$ largest element is $4$, and $2^{th}$ largest element is $3$, and $k^{th}$ (i.e. $4^{th}$) largest element is $1$. So for your question, $n^{th}$ largest element for a min-heap $\mathcal{H}$ of size $n$ is equal to $1^{th}$ smallest element in $\mathcal{H}$, because of $\mathcal{H}$ is min-heap, additionally by definition of min-heap, smallest element appear in root of $\mathcal{H}$ , otherwise it contradict with property of min-heap, because it's provable that $k^{th}$ smallest element in $\mathcal{H}$ can go down at most $k$ levels.

Note that, we can conclude that $k^{th}$ largest element of a min-heap with size $n$ equal to $n-(k-1)$ smallest element.

Source Link
ErroR
ErroR
  • 2k
  • 5
  • 22

Consider the following increasing sorted sequence with size $k=4$ $$ \langle 1,2,3,4 \rangle$$ $1^{th}$ largest element is $4$, and $2^{th}$ largest element is $3$, and $k^{th}$ (i.e. $4^{th}$) largest element is $1$. So for your question, $n^{th}$ largest element for a min-heap $\mathcal{H}$ of size $n$ is equal to $1^{th}$ smallest element in $\mathcal{H}$, because of $\mathcal{H}$ is min-heap, additionally by definition of min-heap, smallest element appear in root of $\mathcal{H}$ , otherwise it contradict with property of min-heap, because it's provable that $k^{th}$ smallest element in $\mathcal{H}$ can go down at most $k$ level. We can conclude that $k^{th}$ largest element of a min-heap with size $n$ equal to $n-(k-1)$ smallest element.