The tag has no wiki summary.

learn more… | top users | synonyms

1
vote
0answers
24 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 ...
1
vote
1answer
21 views

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

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 O(n) because you will have to go through each and every single ...
1
vote
1answer
75 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 ...
1
vote
1answer
40 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
19 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 ...
4
votes
0answers
51 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 ...
1
vote
1answer
182 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 ...
8
votes
4answers
3k 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 runtime complexities of each?
-2
votes
1answer
58 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 ...
2
votes
0answers
49 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
42 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
50 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
64 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)$. ...
2
votes
1answer
198 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 ...
2
votes
1answer
51 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
80 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
110 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 ...
0
votes
1answer
2k 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? ...
3
votes
0answers
123 views

Expected depth of modified kind of treap

If we have $n$ elements $s_1, \dots, s_n$ and build a kind of treap (tree-heap) out of it. Each $s_k$ has a priority, which is an integer in $\{ 1, 2, 3 \dots, \lceil \log n \rceil\}$. Since the ...
1
vote
2answers
6k views

Heap - Give an $O(n \lg k)$ time algorithm to merge $k$ sorted lists into one sorted list

Most probably, this question is asked before. It's from CLRS (2nd Ed) problem 6.5-8 -- Give an $O(n \lg k)$ time algorithm to merge $k$ sorted lists into one sorted list, where $n$ is the total ...
0
votes
1answer
4k views

How to perform bottom-up construction of heaps?

What are the steps to perform bottom-up heap construction on a short sequence, like 1, 6, 7, 2, 4? At this link there are instructions on how to do for a list of ...
3
votes
1answer
98 views

When two siblings in a heap are equal, how do you bubble down?

I have a heap where both child nodes of the root are 10, and I'd like to perform an operation to remove the min value 9. I proceed to replacing the root with its next of kin, 18. However when I ...
7
votes
3answers
6k views

Increase-key and decrease-key in a binary min-heap

In many discussions of binary heap, normally only decrease-key is listed as supported operation for a min-heap. For example, CLR chapter 6.1 and this wikipedia page. Why isn't increase key normally ...
2
votes
1answer
163 views

Leftist heap - determining time complexity

The time complexity of merge (union) operation is said to be $O(\lg (n_1 + n_2))$, where $n_1$ and $n_2$ are the numbers of elements in the merged heaps, respectively. I do not understand this - the ...
2
votes
1answer
2k views

Is search a binary heap operation?

According to the Wikipedia page, search is "not an operation" on binary heaps (see complexity box at top-right). Why not? Binary heaps may not be sorted, but they are ordered, and a full graph ...
3
votes
2answers
950 views

Finding the height of a d-ary heap

I would like to find the height of a d-ary heap. Assuming you have an Array that starts indexing at $1$ we have the following: The parent of a node $i$ is given by: ...
2
votes
1answer
278 views

MinHeap represented by an array - two simple statements

I'm trying to prove/disprove two statements. I just want to make sure with you I'm on the right line. These are the following statements: Preface : Let A[n] be an array of min-heap (a min-heap ...
1
vote
1answer
304 views

Input that causes an operation on a binomial heap to run in $\Omega(\log n)$ time?

I was studying binomial heaps and its time analysis. Are there any inputs that cause DELETE-MIN, DECREASE-KEY, and DELETE to run in $\Omega(\log n)$ time for a binomial heap rather than $O(\log n)$?
5
votes
1answer
1k views

Potential function binary heap extract max O(1)

I need help figuring the potential function for a max heap so that extract max is completed in $O(1)$ amortised time. I should add that I do not have a good understanding of the potential method. I ...
2
votes
1answer
466 views

What is the purpose of Mark field in Fibonacci Heaps?

In Fibonacci heaps, we keep a mark field for every node in the heap. Initially all the nodes are unmarked. Once a node is deleted, its parent is marked. If a node is deleted and its parent is already ...
2
votes
1answer
390 views

Determine whether the $k^{th}$ smallest element in max-heap is greater than a given number

A set of numbers is stored in a max-heap. We want to find an algorithm with $O(k)$ time complexity to check if $k^{th}$ smallest element is greater than an arbitrary given number.
2
votes
2answers
4k views

Deletion in min/max heaps

I think I'm confused about deletion in heaps, and since I have an exam today, I'm looking for your help to correct me. I will post photos since it will makes it a bit more clear. Note(forget about ...
1
vote
2answers
714 views

Extract Max for a max-heap in $\log n + \log\log n$ comparisons

Given a max heap with extract-max operation. The basic version takes $2 \log n$ comparisons. How can I make the running time just $\log n + \log\log n$ comparisons? How about $\log n + \log\log\log n ...
1
vote
2answers
2k views

How can I prove that a build max heap's amortized cost is $O(n)$?

Suppose a build max-heap operation runs bubble down over a heap. How does its amortized cost equal $O(n)$?
12
votes
1answer
805 views

How many max heaps are there?

How many different max-heaps can I form using a list of $n$ integers. Example: list [1,2,3,4] and max-heap is 4 3 2 1 or ...