Questions tagged [heaps]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
3
votes
1answer
2k views

Find k maximum numbers from a heap of size n in O(klog(k)) time

I have a binary heap with $n$ elements. I want to get the $k$ largest elements in this heap, in $O(k \log k)$ time. How do I do it? (Calling deletemax $k$ times yields a $O(k \log n)$ complexity. ...
16
votes
3answers
36k views

Increase-key and decrease-key in a binary min-heap

In many discussions of binary heap, normally only decrease-key is listed as supported operation for a min-heap. For example, CLR chapter 6.1 and this wikipedia page. Why isn't increase key normally ...
1
vote
1answer
309 views

Is this a legal Fibonacci heap?

Imagine a Fibonacci heap with 1 tree: a root node, 4 child nodes (to that root node), with 2 of them being leaves and the other 2 having 1 child each (7 nodes total). Is this a legal Fibonacci heap? ...
95
votes
5answers
108k views

What's the difference between a binary search tree and a binary heap?

These two seem very similar and have almost an identical structure. What's the difference? What are the time complexities for different operations of each?
15
votes
2answers
29k views

Heap - Give an $O(n \lg k)$ time algorithm to merge $k$ sorted lists into one sorted list

Most probably, this question is asked before. It's from CLRS (2nd Ed) problem 6.5-8 -- Give an $O(n \lg k)$ time algorithm to merge $k$ sorted lists into one sorted list, where $n$ is the total ...
19
votes
1answer
7k views

How many different max-heaps exist for a list of n integers?

How many different max-heaps exist for a list of $n$ integers? Example: list [1, 2, 3, 4] The max-heap can be either 4 3 2 1: ...
5
votes
3answers
47k views

Best and worse case inputs for heap sort and quick sort?

So given an input of lets say 10 strings, what way can we input these so we get the best or worst case for these two given sorts? ...
1
vote
1answer
314 views

Show that the running time of the build_heap function is $O(n)$

Given the following two functions, prove that the build_heap function, which transforms an array A into a max-heap-sorted array A' runs in $O(n)$. ...
5
votes
1answer
385 views

Why clear the child's and not the parent's mark in Fibonacci heaps?

According to Cormen et al.'s Introduction to Algorithms chapter 21 on Fibonacci heaps (3rd edition), the FIB-HEAP-LINK($H$, $y$, $x$) clears mark of $y$ which will in the end be the child on the ...
3
votes
1answer
108 views

Proving that converting min-heaps to max-heaps requires time Ω(n)

Suppose I have a min-heap SH stored inside an array. I can perform the operations: view-min(SH) in $O(1)$ extract-min(SH) in $O(\log n)$ insert(SH) in $O(\log n)$ is-empty(SH) in $O(1)$ If I want to ...
2
votes
1answer
1k views

Finding the $k$-smallest elements in a min-heap

Given a min-heap $H$, I am interested in finding the $k$ smallest elements efficiently. The simplest solution would be to call delete-min $k$ times which would give us the solution in $O(k \log n)$ ...
2
votes
1answer
142 views

Build max heap in which all the nodes at certain level are less than all the nodes at the level before them

Max-heap is called a "strong" max-heap if all the nodes at certain level are less than all the nodes at the level before them. What is the most efficient way to build such a heap from a given array? ...
1
vote
3answers
200 views

Why is heap insert O(logN) instead O(n) when you use an array?

I am studying about the arrays vs heap for make a priority queue For check the heap implementation I am reviewing this code: Heap , but I have the following question. Heap is based on array, and ...
1
vote
1answer
1k views

Best way to merge 2 max heaps into a min heap

Assume we have 2 max heaps, each with n nodes. We want to merge these 2 heaps and build a min heap. What is the best way to do this? The easiest way is to consider 2 max heaps an array with $2n$ ...
1
vote
2answers
460 views

The time complexity for finding the kth smallest number in a min-heap [duplicate]

Suppose that $k < \sqrt n$, what is the time complexity to find the $k_{th}$ smallest number in a min-heap? I thought that we can remove the root element for k times and each time we apply heapify?...