A message from our CEO about the future of Stack Overflow and Stack Exchange. Read now.

Questions tagged [heaps]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
2
votes
1answer
82 views

Dijkstra without decrease key

I was reading though this paper, which suggests using dijkstra without edge relaxation, but to rather to just insert new nodes, cf page 16 for the pseudo code. But to me the code looks wrong. I think ...
1
vote
1answer
41 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 ...
0
votes
1answer
50 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 ...
1
vote
0answers
17 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_{...
0
votes
0answers
23 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
48 views

Heap down - What is math logic and intuition behind $\sum_{i=1}^{\log n}(\log n - i) \times 2^i $

In heap (bubble down) we have the formula : \begin{eqnarray*} \sum_{i=1}^{\log n}(\log n - i)\times 2^i & = & \log n\sum_{i=1}^{\log n}2^i -\log n\sum_{i=1}^{\log n}i\times2^i \\ & = &...
4
votes
4answers
2k views

Build-Max-Heap: Why Start i at floor(A.length/2) rather than A.length?

Taken from CLRS third edition, a procedure is given for Build-Max-Heap ...
0
votes
1answer
315 views

How to get all in constant time?

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

Clarification about conclusion of $Θ(nlogn)$?

Why the first part of formula is equal to $2 * 2^2 + ... + 2^{log(n)} = 2^2 + 2^3 +...+ 2^{log(n)} = 2^3 +...+ 2^{log(n)} =... +2^{log(n)}$ What is the logic behind ($2^{log n +1} - 2{log n}$) ? I ...
-1
votes
1answer
39 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 ...
97
votes
5answers
110k views

What's the difference between a binary search tree and a binary heap?

These two seem very similar and have almost an identical structure. What's the difference? What are the time complexities for different operations of each?
2
votes
1answer
1k 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 ...
0
votes
2answers
39 views

inserting into min heap

These are the instructions I been given : What does the array look like at each step when inserting "2" into the following min-heap? Give your answer as comma-separated numbers, with a ...
4
votes
2answers
169 views

If a min heap of [n] is stored into an array, what are the minimum and maximum values for an element at a given index?

If we store a min heap of $n$ elements, $\color{Blue}{[1,2, \dots n]}$ into an array, then what can be minimum value present at any index $i$ and maximum value present at any index $i$. (elements are ...
1
vote
1answer
50 views

Why is building a heap $\mathcal O(n)$ and not $\theta(n)$?

From what I see online, all seem to suggest that heapifying takes $\mathcal O (n)$ time, but it seems like it should always takes $\theta(n)$ time, even in the best case. Is something wrong with my ...
1
vote
1answer
50 views

How to prove the performance, Big Omega ,of building a binary heap using recursive method is Ω(nlog(n))

We can learn the big-O of building a binary heap using recursive method is O(n log n) from wiki "This approach, called Williams’ method after the inventor of binary heaps, is easily seen to run in O(n ...
0
votes
1answer
32 views

3-heap max heap

I have this 3 heap max heap that I need to write the array for it, but I'm not sure how. Would it just be 20,18,13,15,11,12,16,10,9,11,13,2,9?
0
votes
1answer
100 views
3
votes
1answer
109 views

Distinct Binary Heaps

I have $n$ elements out of $n-1$ are distinct. The repeated element is either minimum or maximum element. I need to figure out how many distinct max heaps can be made from it. My analysis : I started ...
1
vote
3answers
293 views

Why is heap insert O(logN) instead O(n) when you use an array?

I am studying about the arrays vs heap for make a priority queue For check the heap implementation I am reviewing this code: Heap , but I have the following question. Heap is based on array, and ...
1
vote
2answers
473 views

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

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?...
4
votes
1answer
160 views

Min Fibonacci Heap - increase key

I have been trying to implementing heap data structures for use in my research work. As part of that, I am trying to implement increase-key operations for min-heaps....
1
vote
1answer
607 views

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

Here is my exercise. FINDLARGEST(k): return the elements in the heap with key >=k" ... "expand the priority queue (max-heap) so that it supports FINDLARGEST(k) in O(m) time, where m is the number ...
0
votes
1answer
70 views

Is there an O(1) solution to find the kth-smallest element in an implicit min-heap?

I know this would be an O(k log n) operation on a traditional heap, and I know there are ways to maintain Kth-smallest over a stream of inserts/deletes for constant-time access... My question though ...
0
votes
2answers
4k views

Proving that an $n$-element heap has at most $\lceil \frac{n}{2^{h+1}-1} \rceil$ nodes

I am having trouble proving that an n-element heap can have at most $\lceil \frac{n}{2^{h+1}-1} \rceil$ nodes. Please note that I am proving a loose bound. First I proved that a complete binary tree ...
3
votes
1answer
64 views

Returning sorted lowest k elements in a binary heap

Given a binary heap of size $n$ and a number $k\le n$. How can I return an array with size $k$, which contains the $k$ lowest elements in the binary heap, so that it will be sorted in the end? The ...
1
vote
2answers
350 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 ...
1
vote
1answer
27 views

What is the index of the leftest child of node in a k-nery heap?

Suppose the root node‘s index is 1, what is the index of the leftest child of a node e in a k-nery heap? What is the parent‘s index of a node in k-nery heap? All questions regarding my problem I ...
2
votes
2answers
58 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
25 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
1answer
43 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 ...
1
vote
3answers
327 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?...
4
votes
2answers
180 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 ...
0
votes
0answers
79 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
126 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
1answer
57 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 ...
0
votes
0answers
88 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 ...
4
votes
1answer
570 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
42 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, ...
20
votes
1answer
7k views

How many different max-heaps exist for a list of n integers?

How many different max-heaps exist for a list of $n$ integers? Example: list [1, 2, 3, 4] The max-heap can be either 4 3 2 1: ...
0
votes
1answer
104 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 ...
3
votes
3answers
133 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 ...
1
vote
1answer
48 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
80 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
68 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
47 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
1answer
184 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
393 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
24 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
256 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+...