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.

0
votes
0answers
50 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
73 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
71 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
91 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
38 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
30 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
45 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 ...
2
votes
2answers
56 views

An algorithm to efficiently insert a list of elements into a binary heap (at once)

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
42 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
34 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
47 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
36 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
105 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
303 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
125 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
63 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
16 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
90 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
60 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
33 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
146 views

How to get all in constant time?

We are planning to design a system where following operations are supported. ...
2
votes
1answer
167 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
218 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
167 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
36 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
41 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
59 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
76 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
232 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
80 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
14 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
602 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
44 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 ...
3
votes
0answers
42 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
755 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
51 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
147 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
260 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
490 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
329 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
908 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
903 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
275 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
486 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
160 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
1k 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 ...
0
votes
0answers
53 views

Proving that a specific Fibonacci heap can't exist [duplicate]

I was asked to describe how I would build a Fibonacci heap that consists of 1 tree with 7 vertices, 2 of them are leaves, and 2 of them are fathers that have a leaf as their son. From what I see, ...
-2
votes
1answer
1k views

Merge 2 Binary Heaps

I want to merge $2$ binary heaps. Which is the fastest algorithm to do so. Also would like to know its time complexity. I know how to do it linear time $O(n)$, I want to know if there is something ...
0
votes
1answer
340 views

Fibonacci Heap / Binomial Heap - Decrease Key

I've been implementing a Fibonacci Heap in C this past week and today I just hit a mental roadblock that I can't figure out. Decrease Key is a function that almost all min heaps have (vice versa with ...
0
votes
1answer
237 views

Using Pascal's Triangle to implement queues and stacks using heaps

I have the following question as homework in an algorithms, analysis and data structures class: And here's an answer I wrote up: A queue is a first-in-first-out data structure. A heap is a data ...