The tag has no usage guidance.

learn more… | top users | synonyms

0
votes
0answers
10 views

What is the time complexity of min-heap based solution to calendar rendering problem

Question: You are given a set of events in a day. Each event has a start and end time. Find the maximum number of concurrent events Solution: First convert events into an array of "Event ...
3
votes
1answer
65 views

Why do you need to fill the first element of array when implementing heap?

I'm looking at Heap data structure implementation from different sources. What I found is that sometimes it's implemented with the first element of array set to magic (default, unused?) value. For ...
1
vote
1answer
55 views

Amortised analysis of binary heap insert and delete-min

I'm trying to figure out how to do amortised analysis of heap insert and heap delete-min using potential function. We can assume, that insert is O(logn) and delete-min is O(logn) too. The goal is ...
-3
votes
1answer
53 views

What is the amortized time complexity of inserting an element to this heap?

Assume you implement a heap using an array and each time the array is full, you copy it to an array double its size. What is the amortized time complexity (for the worst case) of inserting elements ...
3
votes
2answers
95 views

Ideal value of d in a d-ary heap for Dijkstra's algorithm

I stumbled upon the following statement: By using a $ d $-ary heap with $ d = m/n $, the total times for these two types of operations may be balanced against each other, leading to a total time ...
-2
votes
1answer
37 views

Best search in Heap Array

Can someone give me the best search algorithm in a max heap? In particular simply implemented as an array. I knew it has complexity of $O(N)$ but it can be done better. For example, if $A[i] < \...
0
votes
1answer
57 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
69 views

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

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
53 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
68 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
79 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
39 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
65 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
29 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 ...
0
votes
0answers
188 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 ...
0
votes
1answer
56 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
32 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 ...
3
votes
1answer
80 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. ...
0
votes
1answer
81 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
61 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 ...
4
votes
1answer
101 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
342 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
130 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
114 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 (...
1
vote
1answer
116 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
193 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 ...
1
vote
1answer
169 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
167 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
131 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
75 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
329 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
199 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
133 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
166 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
156 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
114 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
120 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
501 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
576 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
65 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
119 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
271 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
428 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
106 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
616 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 ...
37
votes
5answers
33k 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
172 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
92 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
55 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
70 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 ...