The heaps tag has no wiki summary.
-2
votes
2answers
38 views
how to find whether memory was allocated from stack or from heap memory? [closed]
Given a variable, how can we find whether it was allocated from stack or from heap memory?
0
votes
1answer
97 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
47 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
686 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
49 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
108 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 ...
2
votes
2answers
82 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
77 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
79 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
160 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
93 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 ...
1
vote
1answer
167 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
297 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
198 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
603 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)$?
7
votes
1answer
195 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
...
