Kth largest element of a Min Heap of size K is always root element

Question

Why the Kth largest element of a Min Heap of size K is always root element of the Min Heap ? How to prove this ?

Answer 1

Let's assume that the heap $k$-th largest element is unique otherwise your assertion is false (consider an heap consisting of only two identical elements).

The $k$-th largest element of a min-heap of size $k$ is the minimum element and therefore your question is equivalent to "why is the minimum element the root of a min-heap?"

Suppose that the minimum element $e$ was not the root of the heap and let $f$ be the element stored in the parent of $e$. By the heap properties we have $f \le e$ but since $f \neq e$ it must be that $f < e$, resulting in a contradiction.

Answer 2

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.