Stack Overflow
Stack Overflow

Questions tagged [binary-heap]

225 questions
64
votes
5 answers

How to remove element not at top from priority_queue?

In my program I need to delete an element from a priority queue that is not at the top. Can that be done? If not, please suggest a way to do so except creating your own heap.
ishan3243
  • 1,870
  • 4
  • 30
  • 49
40
votes
9 answers

Efficient heaps in purely functional languages

As an exercise in Haskell, I'm trying to implement heapsort. The heap is usually implemented as an array in imperative languages, but this would be hugely inefficient in purely functional languages. So I've looked at binary heaps, but everything I…
Kim Stebel
  • 41,826
  • 12
  • 125
  • 142
37
votes
4 answers

Real world applications of Binary heaps and Fibonacci Heaps

What are the real world applications of Fibonacci heaps and binary heaps? It'd be great if you could share some instance when you used it to solve a problem. Edit: Added binary heaps also. Curious to know.
softwarematter
  • 28,015
  • 64
  • 169
  • 263
29
votes
2 answers

How can std::make_heap be implemented while making at most 3N comparisons?

I looked in to the C++0x standard and found the requirement that make_heap should do no more than 3*N comparisons. I.e. heapify an unordered collection can be done in O(N) /* @brief Construct a heap over a range using comparison functor. Why…
Captain Giraffe
  • 14,407
  • 6
  • 39
  • 67
22
votes
3 answers

What is the difference between binary heaps and binomial heaps?

I need to know the main difference between binary and binomial heaps regardless of the their structure difference that binary heaps can have only two child (tree representation) and binomial heaps can have any number of children. I am actually just…
Abdul Samad
  • 5,748
  • 17
  • 56
  • 70
18
votes
6 answers

Finding last element of a binary heap

quoting Wikipedia: It is perfectly acceptable to use a traditional binary tree data structure to implement a binary heap. There is an issue with finding the adjacent element on the last level on the binary heap when adding an element …
Yse
18
votes
2 answers

how to determine if the kth largest element of the heap is greater than x

Consider a binary heap containing n numbers (the root stores the greatest number). You are given a positive integer k < n and a number x. You have to determine whether the kth largest element of the heap is greater than x or not. Your algorithm must…
Prajapat
  • 233
  • 1
  • 2
  • 7
17
votes
3 answers

How to preserve the order of elements of the same priority in a priority queue implemented as binary heap?

I have created a binary heap, which represents a priority queue. It's just classical well known algorithm. This heap schedules a chronological sequence of different events ( the sort key is time ). It supports 2 operation: Insert and Remove. Each…
psihodelia
  • 29,566
  • 35
  • 108
  • 157
14
votes
2 answers

How do I create a BinaryHeap that pops the smallest value, not the largest?

I can use the std::collections::BinaryHeap to iterate over a collection of a struct in the greatest to least order with pop, but my goal is to iterate over the collection from least to greatest. I have succeeded by reversing the Ord…
Nevermore
  • 7,141
  • 5
  • 42
  • 64
14
votes
1 answer

What is the time complexity of constructing a PriorityQueue from a collection?

What is the complexity of Java's PriorityQueue constructor with a Collection? I used the constructor: PriorityQueue(Collection c) Is the complexity O(n) or O(n*log(n))?
Seffy Golan
  • 201
  • 3
  • 9
12
votes
4 answers

binary heap vs binomial heap vs fibonacci heap, regarding performance for a priority queue

Could someone please explain me how should I decide whether to use one or another heap implementation, among the ones mentioned in the title? I would like an answer to guide me on choosing the implementation regarding the performance of the…
Throoze
  • 3,988
  • 8
  • 45
  • 67
11
votes
4 answers

Max-Heapify A Binary Tree

This is one of the interview questions I recently came across. Given the root address of a complete or almost complete binary tree, we have to write a function to convert the tree to a max-heap. There are no arrays involved here. The tree is…
discoverAnkit
  • 1,141
  • 1
  • 11
  • 25
10
votes
2 answers

Heap or Red-Black Tree?

I am willing to use a data structure as an overflow buffer of constant space. I want to have efficient insert but most importantly efficient removal of the min element. I was thinking of using a heap since I have O(log(n)) find_min() and log(n)…
nikosdi
  • 2,138
  • 5
  • 26
  • 35
9
votes
1 answer

Converting a heap to a BST in O(n) time?

I think that I know the answer and the minimum complexity is O(nlogn). But is there any way that I can make an binary search tree from a heap in O(n) complexity?
user1940350
  • 163
  • 1
  • 7
8
votes
3 answers

Asymptotic time complexity of inserting n elements to a binary heap already containing n elements

Suppose we have a binary heap of n elements and wish to insert n more elements(not necessarily one after other). What would be the total time required for this? I think it's theta (n logn) as one insertion takes logn.
user966892
1
2 3
…
14 15