Questions tagged [heaps]

The tag has no usage guidance.

44 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
4
votes
0answers
268 views

Concurrent priority queue with lazy increase-key

I could use a priority queue supporting the find-and-delete-min, and lazy-increase-key operations. The last term is my "...
3
votes
0answers
749 views

How to determine the fewest number of comparisons for Heapsort?

I'm currently doing an exercise that asks to prove that Standard-Heapsort requires at fewest $\frac{1}{8} n \log(n) - O(n)$ comparisons, in its best case. In its average case, Heapsort only requires $...
3
votes
0answers
4k views

Where To Put Duplicates in Max Heap?

Question: Suppose you have a list of integers and it might contain duplicates. Build a Max Heap using this list. Where would the duplicates of the max integer reside in this Max Heap data structure?...
3
votes
0answers
384 views

Expected depth of modified kind of treap

If we have $n$ elements $s_1, \dots, s_n$ and build a kind of treap (tree-heap) out of it. Each $s_k$ has a priority, which is an integer in $\{ 1, 2, 3 \dots, \lceil \log n \rceil\}$. Since the ...
2
votes
0answers
45 views

Is there an efficient way to insert n items into an n^2 sized heap

I am aware of a O(n) algorithm for constructing a new heap of n items, this is better than repeatedly inserting into an empty heap which takes O(nlogn). I would like to know if there is something ...
2
votes
1answer
2k views

Building heaps and heapsort using linked list

I know that linked list is not a appropriate data structure for building heaps but I am interested in knowing the time complexity of building heaps and heapsort using linked list. One of the answers ...
1
vote
0answers
27 views

Modify Fibonacci Heap to Have a Linear Chain of Marked/Unmarked Nodes Only

In CLRS book there is an exercise (19.4-2), the aim of which is to create a linear chain of nodes by a sequence of Fibonacci-Heap operations. I have solved the problem by recursively making a union ...
1
vote
0answers
30 views

relationship between binary numbers and binomial heaps

I understand that a binomial heap can be represented as binary numbers according to the degree of each tree but what exactly is the relationship between inserting a new node into the binomial heap and ...
1
vote
0answers
75 views

finding the parent index in an interval heap (stored on an array) given a child index

an interval heap is a binary tree stored on an array where the size of each node is 2. i would like to be able to find the index of a parent and find one of the child indices given the index of a ...
1
vote
0answers
18 views

How to compute the general term formula for the number of full binary tree heaps that can be formed with distinct elements?

The number of possible heaps that are full binary trees of height $h$ and can be formed with ($n = 2^h - 1$) distinct elements can be computed by recursion: $$ a_h = {2^h - 2 \choose 2^{h - 1} - 1} a_{...
1
vote
1answer
64 views

Max heap and array relation

This question is about max heap and array Suppose there is max heap $h$, with $n$ data items already stored in $h$. An array that is formed by inserting a value larger than all the values in $h$ at ...
1
vote
0answers
106 views

Randomized meldable heap - meld is oversimplified?

On both Wikipedia and the paper it was introduced the randomized meldable heap uses the following procedure to meld two heaps: ...
1
vote
0answers
1k views

To find median of k sorted arrays of n elements each in less than O(n*k*log(k))

How to find median of k sorted arrays each of length n? Note that total elements would be n*k. I know it can be done in O(n*k*log(k)) using merge technique. I am looking for a better time efficient ...
1
vote
0answers
131 views

Probability of finding the maximum element in a heap

You are given a minimum heap, with probability going to left is 50% and going to right is 50%. What is the probability that You will land up on a maximum element in the heap? For this scenario since ...
1
vote
0answers
2k views

Merging two binary heaps in linear time

Given two binary heaps, each represented by a binary tree with 2k-1 elements, design an algorithm to merge the two heaps into one heap in linear time. I've been having some difficulty in solving ...
1
vote
0answers
217 views

Who first invented and analysed algorithm of finding median in a stream of integers using two heaps?

There is popular problem: Given that integers are read from a data stream, find the median of elements read so far in an efficient way. One of possible solutions: Use max-heap for left heap (i....
1
vote
0answers
367 views

Potential method analysis for Insert and Extract-max on a Max heap data structure

Suppose that you do some sequence of operations on a max heap, in this case only Insert and Extract-max. Whenever the heap ...
1
vote
0answers
357 views

Complexity of using Extract-Max to extract n/2 elements from a max-heap with n distinct elements

I've been given the following question and I've been finding it hard to give a good answer: Prove or disprove: given a max-heap with n distinct elements, using Extract-Max to extract n/2 of the ...
0
votes
0answers
15 views

How to pick a random index in an array based on the index's value?

While solving a problem on leetcode, I used a heap to give the largest probable value. The problem statement is as follows: Given an array w of positive integers, where w[i] describes the weight of ...
0
votes
1answer
10 views

Method to change value in a key for a min heap

How would you write a method to change the value of a min heap where bool changeKey(int oldKey, int newKey). The keys are unique, no duplicate keys are permitted. If there is a key in the heap with ...
0
votes
0answers
27 views

creating a binomial heap with only pointer object references

I have a problem where I must make a binomial heap in Python. I have almost all of the methods working except for the bubbleUp method. The problem I am having is ...
0
votes
0answers
20 views

Is It Of Much Practical Use To Actually Use Fibonacci Heap Over Min Heap In Dijkstra Algorithm?

I know that to get the best technical running time in Dijkstra's shortest path algorithms, using a Fibonacci Heap is the correct way to go. However, the internet and in CLRS state that Fibonacci Heap ...
0
votes
1answer
20 views

reordering a max heap that the values of one of her subtrees has been changed

Let $H$ be a max binary heap with $n$ elements (vertexes). Pick a vertex $z$ in the heap with height of $k$ ($0<k<\lg n$) To every element in the sub heap of $z$ we add the constant value $c &...
0
votes
0answers
29 views

Is it necessary that Minimum/Maximum Heap must be a Binary Heap?

I find this extremely wrong, that a lot of books, articles, video tutorials, online courses or trainers define Minimum/Maximum Heap data structure as a particular type of the Binary Heap data ...
0
votes
0answers
25 views

Quick question about max heap

Suppose that we have a max heap and that it contains duplicate values .Is it always true that nodes with same value are adjacent(neighbors)?I think it is true because if there was any other node being ...
0
votes
0answers
36 views

Efficient way to convert d-ary to binary heap

Even though a general-purpose algorithm is desired, I'm specifically interested in the case that d is 4 (convert 4-ary to 2-ary).
0
votes
1answer
64 views

Time complexity of a 2-heap question

The problem statement is pretty straight forward: given an array of integers and a window size, return an array of doubles of the median of each window. arr = 1, 3, 5, 10, 6, 9, 2 k = 3 would yield ...
0
votes
0answers
24 views

faster heap construction cost equation

can someone try to explain the following formula? I don't understand what does "<=n" and "<=2n" mean in this formula , it is my first time look at summation formula with inequality signature. ...
0
votes
1answer
289 views

heap data structure complexity

I'm trying to count running time of build heap in heap sort algorithm ...
0
votes
0answers
32 views

When inserting an element in a priority queue and the heap size is already at max capacity, should you output an error OR increase the array size?

I'm currently learning about how to implement priority queues using heaps, but I've hit a wall while trying to implement the insertion operation. Assume that the size of the array storing the ...
0
votes
0answers
95 views

Alternative proof of the fact that heapify can be linear-time

As an exercise, I'm trying to prove by myself that constructing a binary heap from an array in-place can be $O(N)$. I've come up with an idea, but I'm not sure about its correctness. Firstly, I ...
0
votes
0answers
149 views

Binary search on a path of minimum heap

WhereTo(H,X) is searching for the place to set X (an integer) in a minimum heap-H. The function is executing a binary search on a path of a heap. Assumption: We have the specific path because it ...
0
votes
0answers
19 views

Why can't popmin in binomial heap just take the main root value?

Why is there a need to scan each root node of the binomial trees in a binomial heap to find the minimum? For example, why can't the true root of the binomial heap, the one that leads to the root ...
0
votes
0answers
49 views

Number of Minheaps Possible

The number of possible min-heaps containing each value from {1,2,3,4,5,6,7} exactly once is: My approach went like this: fixing 1 in the root for the remaining 6 elements we can choose 3 of them and ...
0
votes
0answers
85 views

Treaps are expected weight-balanced?

In a previous question there was a definition of weight-balanced and a question regarding red-black trees. This question is to ask the similar question, but for treaps. The question is: Is there ...
0
votes
0answers
2k views

Bubble down implementation for min-heap

While going through bubble_down implementation for min-heap in The Algorithm Design Manual By Steven Skiena, since routine ...
0
votes
0answers
546 views

How to build a heap better than Incremental and In-place method using decision tree?

For an array A = [a1, a2, a3, a4] of distinct numbers, I have built heap using binary decision tree by Incremental and In-place method. Incremental method: In-place method: Is there a way to build ...
0
votes
0answers
78 views

Analysis on comparisons in a heap-like sorting algorithm

I've stumbled a heap-like sorting algorithm on the Internet as followed: $\\$ For convenience, given a list of $2^n \; (n \in \mathbb{N^*})$ distinct numbers to be sorted increasingly. Step 1: From ...
0
votes
0answers
229 views

What is the time complexity of min-heap based solution to calendar rendering problem

Question: You are given a set of events in a day. Each event has a start and end time. Find the maximum number of concurrent events Solution: First convert events into an array of "Event ...
0
votes
0answers
520 views

Why is removing the second largest element from a max-heap not in O(log n)?

I have a max PriorityQueue designed using a heap. A function removemax() that removes and returns the element with the largest priority in $\Theta(\log n)$ and a function insert in $\Theta(\log n)$ ...
0
votes
1answer
367 views

How to get all in constant time?

We are planning to design a system where following operations are supported. ...
-1
votes
1answer
73 views

Implement heap using stack data structure

I want to implement a heap using the stack data structure. I have searched a lot on the internet. But I do not get any clue how to implement it. Can you please help me to implement a heap using the ...
-1
votes
1answer
390 views

What is the amortized time complexity of inserting an element to this heap?

Assume you implement a heap using an array and each time the array is full, you copy it to an array double its size. What is the amortized time complexity (for the worst case) of inserting elements ...
-2
votes
1answer
436 views

Min-Heap Insertion Problem

I try to insert 4-9-3-7 and 1 (left to right) into a Min-Heap (using array implementation). Then 5 times Remove Smallest Number from this Min-Heap. how many swap between two elements in array occurred?...