heap Questions
3
Solved
I have no idea how to solve following problem efficiently without using _siftup or _siftdown:
How to restore the heap invariant, when one element is out-of-order?
In other words, update old_val...
9
Solved
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 s...
Rataplan asked 17/10, 2010 at 18:6
2
Solved
How can I configure std::priority_queue to ignore duplicates?
When I add a key that is already contained then this new one should be ignored. (In my case, the priority for the old and the new one ...
Rhoea asked 10/5, 2011 at 18:7
7
Solved
I know it is possible to realize decrease-key functionality in O(log n) but I don't know how?
8
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?
Stare asked 27/5, 2011 at 2:30
7
Solved
I have an array that represents a Max Heap. For example
84 81 41 79 17 38 33 15 61 6
so the root is max. Each mid tier node at index i can have at most two children. They would be at 2*i+1 and 2...
4
Solved
I am not sure how to traverse the tree structure below so that the nodes are always in ascending order. Heapifying the array [9 8 7 6 5 4 3 2 1 0] results in the array [0 1 3 2 5 4 7 9 6 8] which I...
Purl asked 4/3, 2014 at 14:26
2
Solved
For example, given a List of Integer List<Integer> list = Arrays.asList(5,4,5,2,2), how can I get a maxHeap from this List in O(n) time complexity?
The naive method:
PriorityQueue<Integer&...
Latinity asked 27/8, 2021 at 23:48
6
Solved
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...
Ophiuchus asked 24/9, 2013 at 22:34
2
Solved
I was trying to implement a sample program using heap, and I am able to Push and Pop from the Heap. I was able to implement the Push and Pop methods and use them as follows:
import "container/...
Banditry asked 9/8, 2020 at 16:39
8
Solved
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?
Aerobiology asked 24/6, 2010 at 19:15
2
Solved
The definition of heap given in wikipedia (http://en.wikipedia.org/wiki/Heap_(data_structure)) is
In computer science, a heap is a specialized tree-based data structure
that satisfies the heap ...
Apparent asked 16/10, 2012 at 19:52
8
Solved
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...
Urien asked 3/3, 2010 at 16:26
3
If I have a heapq which contains some elements like:
import heapq
class Element(object):
def __init__(self, name, val):
self.name = name
self.val = val
if __name__ == "__main__":
heap = []
...
Les asked 14/8, 2014 at 22:47
4
In the constructor of PriorityQueue, we can pass in a collection like List or Set, which builds the PriorityQueue in linear time.
However, this also means the PriorityQueue will use a default Comp...
Basilio asked 23/11, 2016 at 14:21
9
Solved
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(nl...
7
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?
2
Solved
In CLRS, third Edition, on page 155, it is given that in MAX-HEAPIFY,
"the worst case occurs when the bottom level of the tree is exactly half full"
I guess the reason is that in this case, Ma...
5
Solved
I'm making a Monte-Carlo simulation. And as a part of this task I generate samples uniformly distributed over an interval (0,100).
generate = lambda: uniform(0,100)
The iterations stop when all t...
7
Solved
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, ri...
Gilda asked 3/4, 2009 at 16:58
8
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...
Clique asked 14/8, 2013 at 20:2
3
Solved
I tried watching http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/lecture-videos/lecture-4-heaps-and-heap-sort/ to understand heaps ...
10
Solved
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...
Redding asked 24/10, 2011 at 15:28
2
Solved
From the Python docs:
The latter two functions [heapq.nlargest and heapq.nsmallest] perform best for smaller values of n. For
larger values, it is more efficient to use the sorted() function.
...
3
I'm trying to solve the Top K Frequent Words Leetcode problem in O(N log K) time and am getting an undesirable result. My Python3 code and console output are below:
from collections import Co...
© 2022 - 2024 — McMap. All rights reserved.