# Questions tagged [heaps]

The tag has no usage guidance.

176 questions
Filter by
Sorted by
Tagged with
9k views

### What is the advantage of heaps over sorted arrays?

I'm fairly new to heaps and am trying to wrap my head around why min and max heaps are represented as trees when a sorted array appears to both provide min / max properties by default. And a follow ...
217 views

### How to get this upper bound on worst-case heaps?

I've seen answers on the subjects, however I still don't get such answers. In the Cormen book (Introduction to algorithms) it is explained that the worst case for a $Max-Heapify$ call happens when the ...
326 views

### Can a heap have no elements?

Is it correct to call something with no elements a binary heap? I think it is correct, for one element too, but I'm not sure. It seems to satisfy the definition (from Wikipedia): Shape property: a ...
223 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 ...
139 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 ...
2k 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 ...
342 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 ...
1k 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 ...
505 views