Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [heaps]

The tag has no usage guidance.

2
votes
2answers
41 views

Number of possible heaps on $\{1,…,2^h-1\}$

Let $C_h$ be the number of possible heaps for the set of keys $\{1,...,2^h-1\}$. Determine a recurrence relation for $C_h$ via the substitution method and prove it. Definition A binary tree ...
0
votes
0answers
21 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 ...
1
vote
3answers
67 views

Why is Binary Heap never unbalanced?

My professor asks this question: Binary Search tree has Rotation Method to prevent it from degenerating into a linear structure (unbalanced tree). Why is there no need for such method for Binary Heaps?...
1
vote
1answer
26 views

Priority queue with a buffer for delayed insertion and other tweaks

I was thinking of ways to optimise a (heap-based) priority queue in certain scenarios, like in best-first path search algorithms (Dijkstra, A*, etc.). One possible optimisation is to delay insertions ...
0
votes
0answers
58 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 ...
1
vote
2answers
80 views

Difficulty understanding the solution of heap problem in CLRS book?

I am reading the solution of this problem in CLRS: Show that there are at most $\lceil {n/2^{h+1}} \rceil$ nodes of height $h$ in any $n$-element heap. Solution: All the nodes of height $h$ ...
0
votes
0answers
75 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 ...
3
votes
1answer
142 views

Why use heap over red-black tree?

Heap supports insert operation in $O(\log n)$ time. And while heap supports remove min/max in $O(\log n)$ time, to remove any element (non min/max) heap takes $O(n)$ time. However, red-black tree ...
-1
votes
1answer
39 views

Mergable heap with no key knowledge cannot EXTRACT-MIN in $o(\log n)$ amortized time

We are looking into Fibonacci heaps in class at the moment, but I am stuck with this problem. Let $H$ be a mergable heap structure, by which is meant a data structure, where each element has a key, ...
0
votes
1answer
36 views

Number of possible min heaps

The number of possible min-heaps containing each value from {1, 2, 3, 4, 5, 6, 7} exactly once is -------------- According to me, the answer should be 48. The first element 1 is fixed as root. The ...
0
votes
1answer
47 views

Short Fibonacci Heap

Is it possible to create a Fibonacci Heap that has exactly 5 nodes: one root node and 4 children of that root?. If yes please explain the sequence of operations to do so. If it is not possible then ...
4
votes
2answers
84 views

An algorithm to efficiently insert a list of elements into a binary heap (“bulk insertion”)

I wonder if there is any elegant algorithm for inserting a list of elements into a binary heap (at once) whose performance would be close to that of inserting elements one by one when there are only a ...
1
vote
1answer
43 views

An algorithm to drop low-priority items from a heap-based priority queue

I am looking for an efficient algorithm to drop from a complete binary min heap all items whose weight exceeds a given value. (Or, equivalently, to drop from a priority queue realised by such a heap ...
1
vote
1answer
39 views

heap pop creates unbalanced tree?

say you have a min-heap. Popping removes the root and replaces it with the value of one of the leaves and then heapifies. couldnt this last heapify result in an unbalanced tree? is there something ...
2
votes
1answer
56 views

Prove number of nodes in heap

Consider a variation of the normal heap which we will call the x-heap The x-heap of height $h$ has the following properties: It will have $2^h$ nodes A height of $0$ corresponds to the single root ...
1
vote
1answer
41 views

Heap operating in time $\Gamma^{-1}(n)^2$

I have a priority queue implementation which I claim has the following worst case asymptotic run-times for the given operations: PEEK_MIN …………………………… O(1) POP_MIN…………………………… O( (INVERSE_Γ(n)) ^2). ...
3
votes
3answers
115 views

Complexity of forming a min heap out of a given array with k inversions

If a given heap has $k$ inversions, what is the complexity of making it into a valid min heap? We could define an inversion as a tuple (node, descendant), where the node has a key value strictly ...
2
votes
2answers
304 views

Is there a name for this priority queue data structure?

While watching a sports tournament, I noticed that the tournament tree looks a lot like a heap. I came up with the following data structure: A complete binary tree where the leaves are elements of ...
3
votes
1answer
144 views

d-ary heap implementation vs Fibonacci heap implementation Dijkstra performance comparions

Let's say that Dijkstra’s algorithm with the priority queue using a d-ary heap. if adjusting d, we can try to achieve the best runtimes for the algorithm with d being $\sim |E|/|V|$. Then for a ...
0
votes
1answer
127 views

Why is a heap better than a linked list for implementation of a priority queue?

Using a heap, you have O(log(n)) insertion and O(log(n)) removal. Using a linked list, you have O(n) insertion and O(1) removal. Why is it better to have log-n for both than n for one and constant ...
2
votes
1answer
20 views

How does the equation for min heap array indexing work?

I've been reading about min heaps, currently looking at this article, and I am very confused by something. The article makes the following statement: If a given node is located at index 'x' in the ...
2
votes
2answers
118 views

Finding the k-th smallest ternary sum of elements from three different arrays

The problem goes like this: Given arrays $\{ a_i: 0\leq i \leq n-1 \},\{ b_i: 0\leq i \leq n-1 \} $ and $\{ c_i: 0\leq i \leq n-1 \}$, we want to know what is the $k$-th smallest combination $a_r+...
1
vote
1answer
82 views

Sorting n element using Fibonacci Heap

How can I design a sorting algorithm of n elements using a Fibonacci Heap? Will it be a flavoured version of heap-sort where I replace the heap data-structure with Fibonacci Heap? Your help is ...
1
vote
1answer
36 views

Asymptotic bound of a heap's height

Today I was taught that since the height of a heap cannot exceed $\log n$, it is $O(\log n)$; height in my class was defined as the maximum number of steps in a simple path from a leaf to the root. ...
0
votes
1answer
166 views

How to get all in constant time?

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

Minimum number of nodes in AVL tree

Let T be an AVL tree of height 3. What is the smallest number of entries it can store? Note that a tree with one node (only the root) has the height of zero and stores one element. The only method I ...
7
votes
3answers
221 views

Find common min in logarithmic time

I am looking for a data structure to store a set such that given two instances of size $O(n)$ which are known to have non-empty intersection, the minimum element of the intersection can be found in $O(...
2
votes
1answer
269 views

Heap structure in array, computing parent and child

I am studying data structures from Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein, and in the section of heapsort it talks about a data structure beneath the algorithm : a heap, ...
1
vote
1answer
41 views

Complexity of closest set of points in plane problem

Given a set of points on a plane find the set of $n$ points that are closest to the origin. (Points are pairs of integers.) Input: list of points. Initialize a priority queue $Q$, where ...
1
vote
2answers
47 views

Priority queue of constant size fit for extraction of K highest priority elements

In an algorithm I'm designing, I need to do this cycle on a priority queue of constant size N many times, as quickly as possible: get $K$ highest priority elements (do on them some outside ...
1
vote
0answers
71 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: ...
0
votes
0answers
88 views

proving the median in a min heap can be found in every level

I'm trying to prove that given a min heap with n distinct number with at least 3 nodes, that the median can be found in every level. I thought about trying to break the heap into to heaps according ...
0
votes
1answer
298 views

How to construct a max heap that preserves insertion order for duplicate elements?

I have a priority queue (using a max heap) that preserves insertion order for duplicate priorities, such that equal priorities fall back to FIFO behaviour. I'm doing this by creating a node with the ...
2
votes
1answer
92 views

Why is a Fibonacci-Tree of rank 1 consolidated with one of rank n in this Fibonacci-Heap?

In the solution to problem 2 of this exercise sheet: The height of $n$-node Binomial Heap is always $O(\log{n})$. Show that this is not the case for Fibonacci Heaps by exhibiting, for ...
0
votes
0answers
15 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
2answers
706 views

Worst case time complexity of heap sort

I was learning about heaps, and came to know that the worst case time complexity of heap sort is Ω(n lg n). I am having a hard time grasping this. My reasoning is as follows: ...
0
votes
0answers
45 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 ...
2
votes
0answers
43 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 ...
0
votes
0answers
821 views

Find K largest elements using a priority queue [duplicate]

Say we have a Priority Queue of size 1000 that is implemented using Max Heap. Now if i want to get the top 5 elements, the most laid back method is to poll the maximum 5 times, resulting in a set of ...
2
votes
1answer
52 views

Implementing SUM(i,j) and CHANGE(i,j) in O(log(n)) using a datastructure with O(n) space complexity

I have two operations: $Sum(i,j)$ : Calculate $A[i]+A[i+1]+....+A[j]$ $Change(i,x)$: Set $A[i]=x$ I need to implement these operations in an appropriate data structure using $O(n)$ space ($n$ is ...
0
votes
1answer
165 views

Is it possible to find the nodes larger than k in a min-max heap in O(m) time?

Is it possible to find the nodes larger than $ k $ in a min-max heap in $ O(m) $ time, where $ m $ is the number of nodes larger than $ k $? If it is possible, then how do I implement the rest of the ...
1
vote
1answer
287 views

implementing ExtractMin on a Max-heap in O(log(n)) time

Is it possible to implement extractMin on a Max-Heap in O(log(n)) time, and if so how? Or do you need a more elaborate structure like a max-min heap?
1
vote
1answer
520 views

How to find kth largest element in (max) priority queue in O(k) time

I know there is an a scientific article out there which describes some complicated way of finding the kth smallest element in a min-heap in O(k), but this is for an introductory course on algorithms. ...
0
votes
0answers
347 views

The time complexity for finding the kth smallest number in a min-heap

Suppose that $k < \sqrt n$, what is the time complexity to find the $k_{th}$ smallest number in a min-heap? I thought that we can remove the root element for k times and each time we apply heapify?...
1
vote
0answers
957 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 ...
2
votes
1answer
985 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
1answer
355 views

The maximum number of nodes in a heap tree of degree d and depth k

The maximum number of nodes in a binary tree of depth k is defined by 2^(k+1)-1, but the same rule doesn't appear to work for heap trees of different degrees. Let's say I have the following tree of ...
5
votes
2answers
502 views

Why can't we sort an Array in O(n) using Fibonacci Heap?

If we can insert to a Fibonacci Heap in O(1), and increase-key and find-min in the same W.C time complexity, then why can't we sort an array in time complexity O(n)? Given an array with n elements: ...
0
votes
1answer
170 views

Is there an example of an AVL tree that is taller than a binary heap?

I am curious because I took a quiz and answered false to the question: "The height of an AVL tree may be greater than the height of a binary heap with the same elements." I have been trying to think ...
0
votes
3answers
2k views

How huffman tree uses MinHeap?

As far as I know, a minheap is data structure whose parent node's value is less than child node and maxheap is when parent node is greater than child node. Here they have used minheap. But as the node ...