Questions tagged [heaps]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0
votes
1answer
2k views

Difference between Binomial and Fibonacci heap (marking)

I am confused why Binomial heaps do not utilize marking. Concerning Fibonacci heap children: ...
5
votes
2answers
427 views

Is it possible to build a heap from the root to the leaves?

Most books on data-structures will briefly introduce heaps (aka priority queues) and then move to describe the "trick" allowing heaps to be implemented as arrays. I've been looking for a way to ...
2
votes
1answer
108 views

A heap based problem

I have been struggling with this question from my problem set. I do not want a solution but some hints on how to proceed. You are given a file of numbers which represent the values of associated ...
3
votes
1answer
91 views

How to come up the number of nodes on a given level in heaps?

CLRS asked it's readers to prove that there are at most $\lceil n/2^{h+1} \rceil$ nodes of height $h$ in any n-element heap as an exercise. The principle of Mathematical Induction can be used to prove ...
3
votes
3answers
145 views

Data structure choice for a query-update-delete problem

Given is an initial set of n keys. Each key k is of the form (p, q). Note that both p and q are positive. At any given point, there are two possible actions: 1) Query-Delete: Given a value s as ...
1
vote
1answer
58 views

heapify last 3 lines

I'm following http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/lecture-videos/MIT6_006F11_lec04.pdf Last 3 lines of ...
9
votes
1answer
180 views

Randomized Meldable Heap - Expected Height

Randomized Meldable Heaps have an operation "meld", which we then use to define all other operations, including insert. The question is, what is an expected height of that tree with $n$ nodes? ...
0
votes
1answer
191 views

Running Build-Heap Algorithm on given numbers

I don't fully understand this build-heap function. Lets assume we have array 3, 4, 5, 13, 16, 32. It seems like we swap the parent when it is less than the current A[j] but which number does the ...
1
vote
0answers
2k views

Merging two binary heaps in linear time

Given two binary heaps, each represented by a binary tree with 2k-1 elements, design an algorithm to merge the two heaps into one heap in linear time. I've been having some difficulty in solving ...
2
votes
1answer
1k views

Finding the $k$-smallest elements in a min-heap

Given a min-heap $H$, I am interested in finding the $k$ smallest elements efficiently. The simplest solution would be to call delete-min $k$ times which would give us the solution in $O(k \log n)$ ...
2
votes
1answer
86 views

How many different heaps are there of a given shape?

Let's say we have a tree like this: Suppose we are given $N$ distinct elements, $N$ being the number of vertices in the tree (in this case, $N=13$). In how many ways can we distribute the given $N$...
3
votes
1answer
141 views

Solutions to Diophantine Equations using a Min Heap

I've recently come across this problem: Find all solutions to the equation $a + 2b^2 = 3c^3 + 4d^4$ for which $a, b, c, d$ are all less than $100,000$. Hint: use one min-heap and one max-heap. I ...
0
votes
2answers
3k 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 ...
1
vote
1answer
381 views

Trying to understand max heapify

I tried watching http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/lecture-videos/lecture-4-heaps-and-heap-sort/ to understand heaps and ...
5
votes
1answer
363 views

Why clear the child's and not the parent's mark in Fibonacci heaps?

According to Cormen et al.'s Introduction to Algorithms chapter 21 on Fibonacci heaps (3rd edition), the FIB-HEAP-LINK($H$, $y$, $x$) clears mark of $y$ which will in the end be the child on the ...
1
vote
1answer
3k views

Sorting an already k-sorted array

Can anybody give me some hint on how to do this? I'm not really sure where to start. The problem says: We say that an array $A[1...n]$ is $k$-sorted if it can be divided into $k$ blocks, each of ...
1
vote
1answer
579 views

Lower bound on distinct element heapsort

I've been self-studying algorithms and am currently working on one of the starred exercises from CLRS: Exercise 6.4-5 Show that when all elements are distinct, the best-case running time of heapsort ...
1
vote
0answers
214 views

Who first invented and analysed algorithm of finding median in a stream of integers using two heaps?

There is popular problem: Given that integers are read from a data stream, find the median of elements read so far in an efficient way. One of possible solutions: Use max-heap for left heap (i....
1
vote
1answer
389 views

Getting the sorted sequence from a level-wise sorted min-heap

A heap sorted by levels is a heap which: Every parent is smaller than its children. The nodes in each level are sorted from the smallest to the greatest. I need to describe an algorithm with $O(n)$ ...
0
votes
1answer
620 views

d-ary heapsort analysis

I need to find a tight bound on the number of comparisons in a d-ary heapsort, in terms of d and n (the length of the array we ...
5
votes
1answer
660 views

Heap-like data structure allowing peek at largest & smallest

For the purpose of implementing an optimization algorithm (finding the minimum of a multivariate function) I want to create a data structure that supports the following operations: load from array ...
1
vote
1answer
832 views

The algorithm yields optimal ternary codes

Steps to build Huffman Tree Input is array of unique characters along with their frequency of occurrences and output is Huffman Tree. Create a leaf node for each unique character and build a min heap ...
1
vote
0answers
351 views

Potential method analysis for Insert and Extract-max on a Max heap data structure

Suppose that you do some sequence of operations on a max heap, in this case only Insert and Extract-max. Whenever the heap ...
0
votes
1answer
6k views

Searching through a heap complexity

Pretend you want to search through a max-heap to find a specific element. I know there is no such option but still... Would it take worse case O(n) or O(logn) time? I am assuming O(n) since the ...
0
votes
2answers
1k views

Example of worst case input for Build-Max-Heap

What would be an example of a worst-case input for Build-Max-Heap? What would the "shape" of it "look like"? I'm having trouble getting a feeling for it.
0
votes
1answer
2k views

Build-Max-Heap vs. HeapSort

I'm not sure whether my definition for these 2 terms are correct. Hence, could you help me verify that: HeapSort: A procedure which sorts an array in place. Build-Max-Heap: A procedure which runs in ...
-2
votes
1answer
1k views

Removing arbitrary element from Max Heap

Which of the following strategies is more feasible? Strategy 1: Remove the element from the array, compress the array and reheapify. Strategy 2: Update the value of this node to the current maximum ...
2
votes
1answer
216 views

Using a binary heap to solve an equation

I have to find a solution for this equation: I have to find the set of solutions a, b, c, d for all possible combinations of values 1 <= x <= n. $a^5 + b^5 = c^5 + d ^ 5$ I first thought ...
1
vote
1answer
283 views

Merging Sorted lists using Heap Data Structure

Suppose there are $\lceil\log n\rceil$ sorted lists of $\lceil\frac{n}{\log n}\rceil$ elements each. The time complexity of producing a sorted list of all these elements is: (Hint: Use a heap data ...
0
votes
0answers
484 views

Why is removing the second largest element from a max-heap not in O(log n)?

I have a max PriorityQueue designed using a heap. A function removemax() that removes and returns the element with the largest priority in $\Theta(\log n)$ and a function insert in $\Theta(\log n)$ ...
1
vote
1answer
294 views

Keep k+ties largest elements in a stream

I have $n$ numbers that come one by one, and when the last element comes, I want to output $k$ largest elements and those that are ties with the minimal element from this top-$k$ element. For ...
4
votes
1answer
4k views

Heapsort for sorted input

What is the running time of heapsort when the input array is in increasing order? How about decreasing order? (I came across these questions in CLRS.) Here is what I have done so far ... For the ...
2
votes
0answers
3k views

Where To Put Duplicates in Max Heap?

Question: Suppose you have a list of integers and it might contain duplicates. Build a Max Heap using this list. Where would the duplicates of the max integer reside in this Max Heap data structure?...
0
votes
1answer
88 views

What will trigger a worst time search for a binary heap and what is the run time? [closed]

I thought if the values in a max or min heap is monotonically increasing or decreasing, then this will trigger a worst case run time of $\mathcal{O}(n)$ because you will have to go through each and ...
3
votes
1answer
143 views

LazyHeap data structure with $O(n)$ Insert, Delete, and Return operations

Consider a data structure called LazyHeap that supports the following operations: INSERT(x): Given an element $x$, insert it into the data structure. It has no cost. DELETE(x): Delete $x$ from the ...
3
votes
1answer
2k views

Find k maximum numbers from a heap of size n in O(klog(k)) time

I have a binary heap with $n$ elements. I want to get the $k$ largest elements in this heap, in $O(k \log k)$ time. How do I do it? (Calling deletemax $k$ times yields a $O(k \log n)$ complexity. ...
-1
votes
1answer
1k views

Max heap conversion

In the binary tree shown below, which of the following trees is created after conversion into a (max) heap? There are 4 anwsers to choose : By definition, a max heap is a complete binary tree in ...
4
votes
0answers
261 views

Concurrent priority queue with lazy increase-key

I could use a priority queue supporting the find-and-delete-min, and lazy-increase-key operations. The last term is my "...
2
votes
2answers
2k views

Creating a binomial heap from an array in Θ(n) time

I'm studying binomial heaps. A book tells me that insertion of a node to a binomial heap take $\Theta(\log n)$ time. So given an array of $n$ elements it would take $\Theta(n \log n)$ time to convert ...
92
votes
5answers
105k 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
427 views

Min-Heap Insertion Problem

I try to insert 4-9-3-7 and 1 (left to right) into a Min-Heap (using array implementation). Then 5 times Remove Smallest Number from this Min-Heap. how many swap between two elements in array occurred?...
2
votes
0answers
224 views

Binary heap of size $n$ splitting to 2 heaps of size $n/2$ [closed]

Input: A binary heap of size $n$. $n$ is even. Output: 2 binary heaps of size $n/2$ each. I found this question in a solved algorithms test and the solution said: "There is no better solution than to ...
2
votes
1answer
69 views

Binomial heap multiplying nodes

Input: A max binomial heap $H$, and a pointer to a node $V$. Output: A max binomial heap, where all the children of $V$ are multiplied by 2. I have tried solving this by taking out the node $V$ ...
2
votes
1answer
137 views

Binary heap removal peculiar potential function analysis [closed]

Given the potential function $\phi$, it seems that remove max may take $O(1)$ amoratized, meaning that $n$ removals would take $O(n)$, which can't be, as it means we get a linear time comparison based ...
1
vote
1answer
311 views

Show that the running time of the build_heap function is $O(n)$

Given the following two functions, prove that the build_heap function, which transforms an array A into a max-heap-sorted array A' runs in $O(n)$. ...
3
votes
1answer
551 views

Can we create binomial heaps in linear time?

I'm studying binomial heaps in anticipation for my finals and the CLRS book tells me that insertion in a binomial heap takes $\Theta(\log n)$ time. So given an array of numbers it would take $\Theta(n\...
2
votes
1answer
732 views

What's a good algorithm for deleting multiple elements in a heap?

I have a binary min-heap, size n, and I want to delete a number of elements, identified by some predicate. Any algorithm needs at least n tests of the predicate (preferably, exactly n), so the ...
1
vote
0answers
345 views

Complexity of using Extract-Max to extract n/2 elements from a max-heap with n distinct elements

I've been given the following question and I've been finding it hard to give a good answer: Prove or disprove: given a max-heap with n distinct elements, using Extract-Max to extract n/2 of the ...
0
votes
1answer
752 views

Is this a proper Max Heap Data Structure

I was trying to understand the concept of Max-Heap. And to my understanding its a complete binary tree and each parent has a value greater than its children.The example I was going though had the ...
5
votes
3answers
46k views

Best and worse case inputs for heap sort and quick sort?

So given an input of lets say 10 strings, what way can we input these so we get the best or worst case for these two given sorts? ...