The tag has no wiki summary.

learn more… | top users | synonyms

1
vote
1answer
31 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
392 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
94 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
4k 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
2k 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
83 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 ...
3
votes
3answers
4k 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
0answers
113 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
1k 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
546 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
207 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
236 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
755 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
258 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
324 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
2k 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
1answer
333 views

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

Given a max heap with extract-max operation. The basic version takes $2 \log n$ steps. How can I make it in $\log n + \log\log n$ and how in $\log n + \log\log\log n $? I thought of putting ...
1
vote
2answers
1k 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)$?
11
votes
1answer
554 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 ...