Stack Exchange Network

Stack Exchange network consists of 174 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.

1
vote
1answer
34 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
votes
0answers
31 views

Implementation of Tertiary Heaps [closed]

How would you represent a ternary heap in an array? What is the height of a ternary heap of n elements in terms of n? What is an efficient implementation (in pseudo code) of EXTRACT-MAX in a ...
1
vote
1answer
29 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
41 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
33 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
91 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 ...
3
votes
2answers
302 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
104 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
31 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 ...
1
vote
1answer
10 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
52 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
49 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
28 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
120 views

How to get all in constant time?

We are planning to design a system where following operations are supported. ...
2
votes
1answer
98 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
214 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
89 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
33 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
35 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
45 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
62 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
165 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
61 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
470 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
43 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
620 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
124 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
222 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
422 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
298 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?...
0
votes
0answers
807 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
734 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
227 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
464 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
141 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
940 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
48 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
895 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
315 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
208 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 ...
3
votes
1answer
89 views

Proving that converting min-heaps to max-heaps requires time Ω(n)

Suppose I have a min-heap SH stored inside an array. I can perform the operations: view-min(SH) in $O(1)$ extract-min(SH) in $O(\log n)$ insert(SH) in $O(\log n)$ is-empty(SH) in $O(1)$ If I want to ...
1
vote
1answer
330 views

Given a binary min-heap, getting a sorted array of the $\log n$ smallest elements

Let's say we have a binary min-heap of size $n$, and we want to get an array of the smallest $\log n$ values in the heap, sorted. What is the best complexity that we can get and how do we implement it?...
2
votes
1answer
94 views

Build max heap in which all the nodes at certain level are less than all the nodes at the level before them

Max-heap is called a "strong" max-heap if all the nodes at certain level are less than all the nodes at the level before them. What is the most efficient way to build such a heap from a given array? ...
1
vote
3answers
731 views

Algorithm to find k elements following the median in sorted order

I have the following problem: Given an unsorted array A of size n, print the first k elements in A larger than its median. Here's my approach to the problem: ...
0
votes
0answers
80 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
1answer
352 views

Complexity for checking if an array is a min-d-heap

The problem is this: Let us have an int array of length n. Find an algorithm to determine if the array represents a min-d-heap. My solution: We start from the first index in the array, and compare ...
1
vote
1answer
564 views

Rotations in a treap

I have a treap like the first image and I want to reach the second image to restore min heap order property. I can't understand which kinds of rotations have been done. Image 1 Image 2