Questions tagged [heaps]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1
vote
0answers
15 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 ...
0
votes
2answers
38 views

Is destructuring a heap (taking down a heap) also O(n) like building a heap? If so, can the selection problem be solved by this method in O(n) time?

If we can build up a heap with time O(n), can we take down a heap also by O(n)? (by delete-max repeatedly). Intuitively, it may feel it is, because it is like the reverse of build it up. (Building a ...
0
votes
0answers
24 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 ...
1
vote
0answers
25 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 ...
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).
1
vote
0answers
46 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 ...
0
votes
1answer
58 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
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
50 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
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. ...
2
votes
1answer
126 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 ...
0
votes
1answer
71 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 \\ & = &...
2
votes
1answer
36 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
49 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
vote
1answer
51 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 ...
0
votes
1answer
40 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
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 ...
3
votes
1answer
111 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
1answer
72 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 ...
1
vote
3answers
562 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 ...
0
votes
1answer
181 views

heap data structure complexity

I'm trying to count running time of build heap in heap sort algorithm ...
4
votes
1answer
233 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....
0
votes
1answer
99 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 ...
3
votes
1answer
66 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
1answer
31 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
61 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
29 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
517 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
55 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
92 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 ...
2
votes
2answers
143 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
118 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
781 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
45 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
134 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
60 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
234 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
52 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
101 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
69 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
3answers
140 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
2answers
379 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
191 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
443 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
28 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
282 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+...
2
votes
1answer
144 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
47 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
345 views

How to get all in constant time?

We are planning to design a system where following operations are supported. ...