The tag has no wiki summary.

learn more… | top users | synonyms

1
vote
1answer
60 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 ...
0
votes
0answers
59 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 ...
1
vote
0answers
41 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
38 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
1answer
106 views

Example of worst case input for Build-Max-Heap

Is there a worst-case inputs for Build-Max-Heap? I know there is but I just couldn't paint a clear picture of it in my head.
0
votes
1answer
107 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
29 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
61 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
91 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
62 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
59 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 ...
3
votes
1answer
95 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 ...
1
vote
0answers
76 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 ...
0
votes
1answer
52 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 ...
1
vote
1answer
87 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
77 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
67 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
71 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
279 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 ...
16
votes
6answers
9k 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
79 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
56 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
53 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
69 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
267 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
89 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
92 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
175 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 ...
1
vote
1answer
4k 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
164 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 ...
2
votes
2answers
8k 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
5k 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
109 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 ...
8
votes
3answers
8k 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
217 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
3k 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
1k 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
321 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
330 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
2k 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
583 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
442 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
5k 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
819 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
3k 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
1k 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 ...