Stack Overflow
Stack Overflow

Questions tagged [max-heap]

148 questions
37
votes
4 answers

Can max/min heap trees contain duplicate values?

I'm wondering if a max or min heap tree is allowed to have duplicate values? I've been unsuccessful in trying to find information regarding this with online resources alone.
Vimzy
  • 1,871
  • 8
  • 30
  • 56
13
votes
2 answers

how to get the max heap in python

I use heapq module in python, I find I only can the min heap, even if I use reverse=True I still get the min top heap from heapq import * h=[] merge(h,key=lambda e:e[0],reverse=True) heappush(h, (200, 1)) heappush(h, (300,2)) heappush(h,…
user504909
  • 9,119
  • 12
  • 60
  • 109
12
votes
1 answer

Max heap vs Min heap for kth smallest element

I am having trouble understanding why solutions for finding the kth smallest element uses a Max heap approach. And for the kth largest element a min heap approach. Wouldn't it make more sense to use min heap to find kth smallest element, since the…
user7722505
8
votes
3 answers

Is there a maxheap in the C++ standard library?

I know the std::priority_queue class implements a minheap. Is there a way to use this as a Max heap? Or is there an alternative Maxheap structure? I know I can use the std::make_heap() function on a std::vector with lambda to create my own Maxheap…
OgiciBumKacar
  • 311
  • 1
  • 3
  • 10
8
votes
1 answer

Python: Find running median with Max-Heap and Min-Heap

I'm trying to return the running median for a series of streaming numbers. To do that I use a max-heap (which stores the values on the lower half of the series) and a min-heap (which stores the values on the higher half of the series). In particular…
SergeGardien
  • 137
  • 2
  • 11
6
votes
3 answers

Trying to understand max heapify

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 and heapsort but did not find this clear. I do not…
DoubleBass
  • 1,143
  • 4
  • 12
  • 29
6
votes
1 answer

Pop max value from a heapq python, Is there a max-heap in Python?

Possible Duplicate: What do I use for a max-heap implementation in Python? I am trying to implement in some way the heapq of python but for a max-heap. A solution is using the (-1) and multiple with numbers of the queue but that doesn't help me…
Mike B
  • 1,522
  • 1
  • 14
  • 24
3
votes
1 answer

Build a max heap for an array

I have a homework question that says: Problem 1: Given the array [ 22 | 25 | 71 | 24 | 18 | 5 | 27 | 32 | 104 | 8 | 23 | 66 ] Build a max-heap for the array. Show all steps without skipping any details. This is my understanding about the…
Tono Nam
  • 34,064
  • 78
  • 298
  • 470
3
votes
1 answer

Expedition Problem from SPOJ. Using heap data structure

Problem Expedition A group of cows grabbed a truck and ventured on an expedition deep into the jungle. Being rather poor drivers, the cows unfortunately managed to run over a rock and puncture the truck's fuel tank. The truck now leaks one unit of…
Son Nguyen
  • 31
  • 1
3
votes
1 answer

comparators in sort function and priority queue c++

In C++ Sort function, the third optional parameter is a comparator used to sort the objects. If we pass in less as the comparator, we will get objects in increasing order. (if the comparator is evaluated to be true, the positions won't be changed,…
Zixin Liu
  • 59
  • 5
3
votes
2 answers

Python built-in heap (heapq): Odd behavior if inverted (max-heap)

I'm trying to use the Python (2.0) built-in min-heap data structure from the heapq module (https://docs.python.org/3/library/heapq.html) to build a max-heap. To do that I simply use the negative of the numbers I need to push into my heap. Using this…
SergeGardien
  • 137
  • 2
  • 11
3
votes
2 answers

Max Heapify-pseudocode

I'm confused on one part of this pseudocode for Max Heap Sort. What does down to 2 mean? HeapSort(A) Build-Max-Heap(A) for i <-- length[A] down to 2 do exchange A[1] <---> A[i] heap-size[A] = heap-size[A] -1 Max-Heapify(A,1)
user7941837
  • 33
  • 1
  • 3
3
votes
3 answers

Searching the 7th largest element in a max-heap?

So my friend and I are not seeing eye to eye in this question. It asks for the time complexity of searching for the 7th largest element in a max-heap of n elements? I'm of the opinion that it should be O(n) and she is of the opinion it should be…
bigbong
  • 541
  • 4
  • 12
3
votes
3 answers

max heap and insertion

I have the an integer array of size 10. I need to draw the complete binary tree which I did. Now I need to insert the three other elements using siftup procedure. Show the max heap following each insert. I m not sure what is that show the max heap…
johnnily
  • 153
  • 2
  • 5
  • 11
3
votes
1 answer

How worthwhile is this optimization for Heapsort?

The traditional Heapsort algorithm swaps the last element of the heap with the root of the current heap after every heapification, then continues the process again. However, I noticed that it is kind of unnecessary. After a heapification of a…
SexyBeast
  • 7,913
  • 28
  • 108
  • 196
1
2 3
…
9 10