Stack Overflow
Stack Overflow

Questions tagged [minmax-heap]

A minmax heap is a type of double-ended priority queue data structure based on a complete binary tree.

22 questions
48
votes
7 answers

Java implementation for Min-Max Heap?

Do you know of a popular library (Apache, Google, etc, collections) which has a reliable Java implementation for a min-max heap, that is a heap which allows to peek its minimum and maximum value in O(1) and to remove an element in O(log n)?
Yuval Adam
  • 161,610
  • 92
  • 305
  • 395
5
votes
1 answer

Delete-max operation in a min-max heap

I am implementing a min-max heap, a type of double-ended priority queue. You can look here here for more information about min-max heaps. The code for insertion and delete-min operations are simple and available on the net. But, I am also trying…
AvinashK
  • 3,309
  • 8
  • 43
  • 94
2
votes
2 answers

How do I perform a deletion of the kth element on a min-max heap?

A min-max heap can be useful to implement a double-ended priority queue because of its constant time find-min and find-max operations. We can also retrieve the minimum and maximum elements in the min-max heap in O(log2 n) time. Sometimes, though, we…
nbro
  • 15,395
  • 32
  • 113
  • 196
2
votes
1 answer

Maxheap vs priorityqueue confusion

Suppose we want to sort a hashmap based on the value. We implement a priorityQueue with comparator to do this. As a result, the resulting pq is sorting from the largest to the smallest from index 0 to end. Here is the…
kkk
  • 35
  • 7
1
vote
3 answers

Print k largest elements in a max heap sized n, in klog(k) complexity

I tried writing an algorithm that prints the k largest elemtns of a max heap but I cannot do it in the right complexity. This is the Pseudo-code I wrote- Print_k_largest(A[1,…,n],k): If k>Heapsize(A):Error i=1 insert[B,A[i]) print(B[1]) k-=1 While…
DR_2001
  • 29
  • 4
1
vote
1 answer

transforming max-heap into min-heap with heapfy

I'm trying to heapfy a max-heap i've got into a min-heap. For some reason i'm not getting the result i expect. i've built my max-heap and the array contents of it are showing as expected: 60 50 30 20 40 10 When trying heapfy the above array and…
Zolak
  • 23
  • 3
1
vote
2 answers

in binary max heap, isn't a parent node bigger than its children?

I got wrong on this question because the question says in Binary Max Heap, "If y is a node in the right subtree of node x, then y.key >= x.key." I attached the screenshot of the question below. Binary Max Heap Question if y is a node in the subtree…
jinmountain
  • 15
  • 5
1
vote
1 answer

Heapsort: Build max heap procedure explanation

i'm trying to understand the code to sort an array using Heap Sort (ref - https://www.sanfoundry.com/java-program-implement-heap-sort/) "maxheap" function uses this calculation to get the left & right children of the Node (the same is used in…
Karan Alang
  • 869
  • 2
  • 10
  • 35
1
vote
1 answer

How to build a Min-Max Heap in O(n) time complexity?

I found the topic of min-max heap on Wikipedia. I was wondering if there is any way of building this min-max heap in O(n). I know you can do this with both min heap and max heap, but I'm not sure what would be the approach for this. Inserting an…
Cherry
  • 81
  • 2
  • 10
0
votes
1 answer

Finding the maximum and minimum value inside a "max-min" heap in constant time

So, I was given an "opposite structure" to a "min-max" heap, that is called a "max-min" heap. For every node in even depth, the value of the node is greater or equal to the value of its children. For every node in odd depth, the value of the node…
Rami Mamadov
  • 11
  • 3
0
votes
1 answer

Anomaly in Priority Queue Custom Sort in C++

I went through a couple of StackOverflow and Codeforces articles for custom sorting priority queues in C++. By default the C++ implementation is a MaxHeap , so it would output elements in decreasing order. I minor tweak adding greater would pop…
eternityparadigm
  • 375
  • 3
  • 10
0
votes
1 answer

Can you assign a NULL pointer variable to a pointer variable?

So I was working on the Max Heap Tree with link representation on C++. Since I cannot upload the code as it is pretty long but while I was debugging I realized that the execution will stop at the expression where it assgins Null pointer to a…
changgong lee
  • 1
  • 1
0
votes
1 answer

how can I adjust my priority queue alphabetically? I’ve obtained the frequency, how can I take that word and compare it alphabetically with this heap?

My issue is the logic to get the ordering correct--alphabetically. I just don't know what technique I can use to keep the values that are at most at the top and if they have the same occurrence and return the list in that alphabetic order. Input:…
Woody P Lucas
  • 77
  • 1
  • 5
0
votes
2 answers

Min Max Priority Queue for Scala

I am searching a library with a MaxMinPriorityQueue like guava's one. As I can't use it because sbt fails when I add the dependency like this: "com.google.guava" %% "guava" % "24.0-jre" Its seems there is no build for scala, as it can be…
Alejandro Alcalde
  • 5,990
  • 6
  • 39
  • 79
0
votes
1 answer

Deleting min and max from min-max queue class in less than linear time

I'm implementing a queue class that has both a popMin and popMax method. So far I have it working with two priority queues, but even though a remove is log(n) time, I have to remove from the other queue as well which is linear. I know that a double…
ecain
  • 1,282
  • 5
  • 23
  • 54
1
2