New answers tagged

3

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}$...


2

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 ...


1

To keep it short and simple, the answer is yes. BFS, in addition to the set of visited nodes, makes use of queue for unprocessed nodes (and at each step in the process, you enqueue the unvisited neighbors of the current node, etc.). Also, for the BFS that keeps track of the path, you've to store the pointer to the predecessor node. Whereas DFS (which passes ...


1

In the case of the binary tree, and assuming your binary tree is balanced, yes, I think you will be using more space at any given time in general with BFS. DFS would be allocating and releasing memory space, while BFS would be holding memory increasingly as it goes down the tree. BFS would be simplified because you don't need really to mark visited nodes as ...


0

There's a linear-time algorithm to reconstruct a binary search tree given a depth-first preorder left-to-right traverse. But it seems to me that what you're looking for is an algorithm which will work with a traverse which only satisfies the property that a parent appears before its children. The algorithm you present is $O(N log N)$ on average, but worst ...


Top 50 recent answers are included