Questions tagged [heap]
A heap (data structure) is a tree that is ordered with respect to depth. When the question concerns process memory set aside for dynamic allocation, tag with heap-memory instead.
heap
1,857
questions
877
votes
19
answers
497k
views
How can building a heap be O(n) time complexity?
Can someone help explain how can building a heap be O(n) complexity?
Inserting an item into a heap is O(log n), and the insert is repeated n/2 times (the remainder are leaves, and can't violate the ...
- 17.8k
443
votes
20
answers
300k
views
What do I use for a max-heap implementation in Python?
Python includes the heapq module for min-heaps, but I need a max-heap. What should I use for a max-heap implementation in Python?
- 21.4k
255
votes
10
answers
194k
views
Find running median from a stream of integers
Possible Duplicate:
Rolling median algorithm in C
Given that integers are read from a data stream. Find median of elements read so far in efficient way.
Solution I have read: We can use a max ...
- 5,431
244
votes
12
answers
247k
views
Priority queue in .Net [closed]
I am looking for a .NET implementation of a priority queue or heap data structure
Priority queues are data structures that provide more flexibility than simple sorting, because they allow new ...
- 14.4k
234
votes
9
answers
43k
views
Why are two different concepts both called "heap"? [duplicate]
Why are the runtime heap used for dynamic memory allocation in C-style languages and the data structure both called "the heap"? Is there some relation?
- 9,419
212
votes
8
answers
126k
views
Heap vs Binary Search Tree (BST)
What is the difference between a heap and BST?
When to use a heap and when to use a BST?
If you want to get the elements in a sorted fashion, is BST better over heap?
- 4,311
132
votes
7
answers
152k
views
Is there a Heap in java?
I am porting a C++ library to Java and I need a heap data structure. Is there a standard implementation or will I need to do it myself?
- 3,358
122
votes
6
answers
69k
views
When would I want to use a heap?
Besides the obvious answer of a Priority Queue, when would a heap be useful in my programming adventures?
- 7,683
113
votes
9
answers
137k
views
How to make heapq evaluate the heap off of a specific attribute?
I wish to hold a heap of objects, not just numbers. They will have an integer attribute in them that the heap can sort by. The easiest way to use heaps in python is heapq, but how do I tell it to ...
- 1,211
102
votes
3
answers
32k
views
What's the difference between heapq and PriorityQueue in python?
In python there's a built-in heapq algorithm that gives you push, pop, nlargest, nsmallest... etc that you can apply to lists. However, there's also the queue.PriorityQueue class that seems to support ...
- 5,394
91
votes
5
answers
30k
views
Worst case in Max-Heapify - How do you get 2n/3?
In CLRS, third Edition, on page 155, it is given that in MAX-HEAPIFY,
The children’s subtrees each have size at most 2n/3—the worst case
occurs when the bottom level of the tree is exactly half ...
- 25.6k
88
votes
6
answers
74k
views
Difference between priority queue and a heap
It seems that a priority queue is just a heap with normal queue operations like insert, delete, top, etc. Is this the correct way to interpret a priority queue? I know you can build priority queues in ...
- 4,817
81
votes
4
answers
83k
views
What is Python's heapq module?
I tried "heapq" and arrived at the conclusion that my expectations differ from what I see on the screen. I need somebody to explain how it works and where it can be useful.
From the book Python ...
- 6,338
77
votes
5
answers
99k
views
What's the time complexity of functions in heapq library
My question is from the solution in leetcode below, I can't understand why it is O(k+(n-k)log(k)).
Supplement: Maybe the complexity isn't that, in fact I don't know the time complexity of heappush() ...
user6617337
72
votes
3
answers
84k
views
Python: delete element from heap
Python has heapq module which implements heap data structure and it supports some basic operations (push, pop).
How to remove i-th element from the heap in O(log n)? Is it even possible with heapq or ...
- 11.1k
71
votes
9
answers
153k
views
Finding the median of an unsorted array
To find the median of an unsorted array, we can make a min-heap in O(nlogn) time for n elements, and then we can extract one by one n/2 elements to get the median. But this approach would take O(nlogn)...
- 5,431
68
votes
6
answers
94k
views
How to delete in a heap data structure?
I understand how to delete the root node from a max heap but is the procedure for deleting a node from the middle to remove and replace the root repeatedly until the desired node is deleted?
Is O(log ...
- 745
64
votes
2
answers
56k
views
Peeking in a heap in python
What is the official way of peeking in a python heap as created by the heapq libs? Right now I have
def heappeak(heap):
smallest = heappop(heap)
heappush(heap, smallest)
return smallest
which ...
- 2,799
62
votes
4
answers
46k
views
Why in a heap implemented by array the index 0 is left unused?
I'm learning data structures and every source tells me not to use index 0 of the array while implementing heap, without giving any explanation why. I searched the web, searched StackExchange, and ...
- 7,789
60
votes
4
answers
50k
views
How to implement O(logn) decrease-key operation for min-heap based Priority Queue?
I am working on an application that demonstrates the Djikstra's algorithm, and to use it, I need to restore the heap property when my elements' value is decreased.
The problem regarding the ...
- 882
59
votes
9
answers
8k
views
What's the relationship between "a" heap and "the" heap?
A heap is a tree data structure where higher levels of the tree always contain greater (or lesser, if it's set up that way) values than lower levels. "The" heap is a bunch of free RAM that a program ...
- 83.4k
52
votes
7
answers
56k
views
How do I find the median of numbers in linear time using heaps?
Wikipedia says:
Selection algorithms: Finding the min,
max, both the min and max, median, or
even the k-th largest element can be
done in linear time using heaps.
All it says is that it can be done, ...
- 92.4k
51
votes
6
answers
19k
views
When should I use make_heap vs. Priority Queue?
I have a vector that I want to use to create a heap. I'm not sure if I should use the C++ make_heap function or put my vector in a priority queue? Which is better in terms of performance? When should ...
- 563
47
votes
7
answers
27k
views
How can I implement decrease-key functionality in Python's heapq?
I know it is possible to realize decrease-key functionality in O(log n) but I don't know how?
zerodx
46
votes
10
answers
30k
views
Is there a PriorityQueue implementation with fixed capacity and custom comparator?
Related questions:
Java PriorityQueue with fixed size
How do I use a PriorityQueue?
get indexes of n smallest elements in an array
Scala: Is there a way to use PriorityQueue like I would in Java?
I ...
- 28k
41
votes
4
answers
27k
views
What is the time complexity of heapq.nlargest?
I was looking at this pycon talk, 34:30 and the speaker says that getting the t largest elements of a list of n elements can be done in O(t + n).
How is that possible? My understanding is that ...
- 940
41
votes
7
answers
28k
views
PriorityQueue/Heap Update
Does Java have an easy way to reevaluate a heap once the priority of an object in a PriorityQueue has changed? I can't find any sign of it in Javadoc, but there has to be a way to do it somehow, ...
- 4,277
40
votes
8
answers
102k
views
Search an element in a heap
I remembered that heap can be used to search whether an element is in it or not with O(logN) time complexity. But suddenly I can't get the details. I can only find getmin delete add and so on.
Can ...
- 25.5k
40
votes
3
answers
29k
views
Is there a standard Java implementation of a Fibonacci heap?
I was looking at the different kind of heap data structures.
The Fibonacci heap seems to have the better worst case complexity for (1) insertion, (2) deletion and (2) finding the minimum element.
I ...
- 3,440
40
votes
4
answers
7k
views
The reason of using `std::greater` for creating min heap via `priority_queue`
I am wondering why for creating a min heap using the priority_queue, the std::greater should be used?
std::priority_queue<T, std::vector<T>, std::greater<T> > min_heap;
To me, ...
- 768
38
votes
5
answers
22k
views
python, heapq: difference between heappushpop() and heapreplace()
I couldn't figure out the difference (other than ordinality of push/pop actions) between functions heapq.heappushpop() and heapq.heapreplace() when i tested out the following code.
>>> from ...
- 3,815
35
votes
8
answers
40k
views
How can I use binary heap in the Dijkstra algorithm?
I am writing code of dijkstra algorithm, for the part where we are supposed to find the node with minimum distance from the currently being used node, I am using a array over there and traversing it ...
- 9,310
34
votes
2
answers
27k
views
O(klogk) time algorithm to find kth smallest element from a binary heap
We have an n-node binary heap which contains n distinct items (smallest item at the root). For a k<=n, find a O(klogk) time algorithm to select kth smallest element from the heap.
O(klogn) is ...
user978837
34
votes
3
answers
41k
views
Algorithm for merging two max heaps?
Is there an efficient algorithm for merging 2 max-heaps that are stored as arrays?
- 2,332
33
votes
4
answers
64k
views
Understanding how to create a heap in Python
The collections.Count.most_common function in Python uses the heapq module to return the count of the most common word in a file, for instance.
I have traced through the heapq.py file, but I'm having ...
- 10.9k
31
votes
3
answers
29k
views
SQL Server heap v.s. clustered index
I am using SQL Server 2008. I know if a table has no clustered index, then it is called heap, or else the storage model is called clustered index (B-Tree).
I want to learn more about what exactly ...
- 45.2k
29
votes
1
answer
11k
views
Argument for O(1) average-case complexity of heap insertion
The claim on the Wikipedia page for binary heaps is that insertion is O(log n) in the worst case, but O(1) on average:
The number of operations required depends only on the number of levels the new ...
- 20.5k
28
votes
3
answers
52k
views
How to implement Priority Queues in Python?
Sorry for such a silly question but Python docs are confusing...
Link 1: Queue Implementation
http://docs.python.org/library/queue.html
It says that Queue has a class for the priority queue. But I ...
- 9,363
28
votes
3
answers
57k
views
Is there an easy way to make a min heap in C++?
I'm very new to C++, and I was wondering if there was a way to make a min heap in C++ from the standard library.
- 3,807
26
votes
8
answers
25k
views
What is the definition for the height of a tree?
I can't seem to find a definitive answer for this, I'm trying to do some elementary proofs on heaps but here's what's throwing me off a little bit:
Is an empty tree valid? If so, what is its height?
...
- 572
26
votes
3
answers
40k
views
Comparator for min-heap in C++
I am trying to make a min-heap1 of longs in C++ using the STL make_heap, etc., but my comparator doesn't seem to be comparing properly. The following is my current comparator:
struct greater1{
...
- 7,600
25
votes
2
answers
107k
views
Heap class in .NET [duplicate]
Possible Duplicate:
Fibonacci, Binary, or Binomial heap in c#?
Is there any class like heap in .NET?
I need some kind of collection from which I can retrieve min. element. I just want 3 methods:
...
- 2,795
24
votes
2
answers
19k
views
Python heapify() time complexity
def heapify(A):
for root in xrange(len(A)//2-1, -1, -1):
rootVal = A[root]
child = 2*root+1
while child < len(A):
if child+1 < len(A) and A[child] > A[...
- 974
23
votes
8
answers
30k
views
How to maintain dictionary in a heap in python?
I have a dictionary as follows:
{'abc':100,'xyz':200,'def':250 .............}
It is a dictionary with keys as a name of a entity and the value is count of that entity. I need to return the top 10 ...
- 7,423
23
votes
2
answers
20k
views
Dijkstra algorithm. Min heap as a min-priority queue
I'm reading about Dijkstra's algorithm in CLRS, Third Edition (p. 662). Here is a part from the book I don't understand:
If the graph is sufficiently sparse — in particular, E = o(V^2/lg V) — we ...
- 6,093
22
votes
8
answers
47k
views
Implement Heap using a Binary Tree
This question has been asked before in Stack Exchange but it went unanswered.
Link to the previously asked question:
Binary Heap Implemented via a Binary Tree Structure
How do I implement heap in a ...
- 1,271
22
votes
5
answers
4k
views
Why are heaps in c++ implemented as algorithms instead of containers?
I was wondering why the heap concept is implemented as algorithms (make_heap, pop_heap, push_heap, sort_heap) instead of a container. I am especially interested is some one's solution can also ...
21
votes
8
answers
46k
views
Is a sorted array a min-heap? What's the minimum value of a max-heap?
I have studied min-heaps and max-heaps, and I have a couple of questions:
Is a sorted array a min-heap?
What is the minimum value of a max-heap?
- 871
20
votes
3
answers
25k
views
easy way to maintain a min heap with stl?
for user defined struct, as I understand, it's easy. Just overload the operator <. However, for int/float etc.., do I really need to overload operator < for int?
Here is what I tried:
#...
- 769
20
votes
3
answers
9k
views
Why is a binary heap better as an array than a tree?
When making a binary max heap, why is it better to implement it as a array based, and not a tree based (tree based as in, each node also having a pointer to it's parent)?
In terms of run time analysis,...
- 42.2k