Stack Overflow
Stack Overflow

Questions tagged [heapq]

A Python module that implements the heap queue algorithm. Use only when the question is specific to this heap implementation, as opposed to heap mechanics in general.

Module documentation: heapq

Alternative, using a different interface: queue.PriorityQueue

See also the language-agnostic tag.

90 questions
37
votes
2 answers

heapq push TypeError: '<' not supported between instances

I am working in python and I have some problem with heapq. When I push an element into the heap I receive this error : TypeError: '<' not supported between instances of 'Point' and 'Point' Point is my internal class. I push a tuple formed by…
Francesco
  • 460
  • 1
  • 4
  • 11
21
votes
1 answer

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[child+1]: child += 1 if…
typing...
  • 934
  • 2
  • 10
  • 25
18
votes
2 answers

Why is heap slower than sort for K Closest Points to Origin?

The coding task is here The heap solution: import heapq class Solution: def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]: return heapq.nsmallest(K, points, key = lambda P: P[0]**2 + P[1]**2) The sort…
Yan Yang
  • 1,804
  • 2
  • 15
  • 37
8
votes
1 answer

How to access the top element in heapq without deleting (popping) it python?

How to access the top element in heapq without deleting (popping) it python ? I need only to check the element at the top of my heapq without popping it. How can I do that.
ibra
  • 1,164
  • 1
  • 11
  • 26
5
votes
1 answer

Why is heapq.heapify so fast?

I have tried to reimplement heapify method in order to use _siftup and _siftdown for updating or deleting any nodes in the heap and maintaining a time complexity of O(log(n)). I did some effort for optimizing my code, But they proved to be worse…
Rahul A Ranger
  • 496
  • 1
  • 5
  • 13
5
votes
2 answers

What is the time complexity of the heapq.merge in python?

I read that the heapq.merge function is specifically used to merge 2 sorted arrays? is the time complexity O(n)? if not what is it and why? Also what is its space-complexity. I was solving the question to merger 2 sorted arrays with 2 pointers and…
Jidnyasa Babar
  • 69
  • 4
5
votes
1 answer

Python: heapq.heappop() gives strange result

I'm trying to use the Python module heapq in my program but I ran into a strange problem using heapq.heappop(). The function does not appear to return the smallest element in the heap. Take a look at the following code: Python 2.7.12 (default, Jul …
jpaulus
  • 53
  • 1
  • 4
3
votes
1 answer

TypeError: on heapq.heapop on python3 but but working in python2

I am working on a genome compression algorithm using variations of Huffman coding. I have the following piece of code in python2: def makeHuffTree(trees): heapq.heapify(trees) while len(trees) > 1: childR, childL = heapq.heappop(trees),…
Manoj Agrahari
  • 31
  • 2
3
votes
2 answers

heapq can't handle tuples having same priority if the item is not comparable

>>> from heapq import heappush >>> heap = [] >>> heappush(heap,(0,{"k":0})) >>> heappush(heap,(0,{"k":1})) Traceback (most recent call last): File "", line 1, in TypeError: '<' not supported between instances of 'dict' and…
xxbidiao
  • 834
  • 5
  • 14
  • 27
3
votes
1 answer

Why is _siftup and _siftdown just the opposite in Python?

From the definition of binary heap in Wikipedia, sift-up is also called up-heap operation, and sift-down is called down-heap. So in heap (complete binary tree), up means from leaf to root, and down means from root to leaf. But in python, it seems…
recnac
  • 3,744
  • 6
  • 24
  • 46
2
votes
1 answer

Does heapq.merge work with Iterator classes?

I'm having an issue using the heapq.merge function with an iterator class. Once the merge function is down to one iterator it finishes with line yield from next.__self__ which in the case of an iterator class, restarts the iterator. The behaviour…
Greg
  • 133
  • 7
2
votes
4 answers

heapq.merge: after merge the result of merge, the original merge is empty

First I created two results of a & b by using heapq.merge, but after mergeing a&b, I found the list of a is empty. >>> a=merge([1,2],[3,4]) >>> b=merge([4,5],[6,7]) >>> list(a) [1, 2, 3, 4] >>> merge(a,b) >>>…
user793584
  • 35
  • 4
2
votes
0 answers

Does the default min() method in python uses heap binary tree implementation to find the minimum value in a list?

Hi so i have a list u = [2,45,0,56,78,13]. We can use min() method to find the minimum value in a list. I was going through the heap binary tree. The python has a module heapq and there is a method heapq.nsmallest() which helps to find the n…
Danish Xavier
  • 1,225
  • 1
  • 10
  • 21
2
votes
1 answer

make a list of the largest two and smallest two items of the same collection using the heapq module two functions nlargest() and nsmallest()

I want to make a list of the largest two and smallest two items in a list of dictionaries based on a dictiony key in this case 'price' - as shown below in the code - using the heapq module two functions nlargest() and nsmallest() i tried this code…
MedAmineMahmoud
  • 83
  • 2
  • 7
2
votes
1 answer

15 puzzle astar search that goes into an infinite loop

I am trying to develop a 15 star puzzle program in Python and its supposed to sort everything in numerical order using the a star search algorithm with the 0 being at the end. Here is my a star algorithm I've developed so far: """Search the nodes…
IMFeeferz
  • 21
  • 3
1
2 3 4 5 6