8. Binary Heaps

MIT 6.006 Introduction to Algorithms, Spring 2020
Instructor: Erik Demaine

Prof. Demaine discusses priority queue interfaces and sorting algorithms. Algorithms include, AVL sort for set AVL trees, selection sort for arrays, insertion sort for sorted arrays, and heap sort for binary heaps.

License: Creative Commons BY-NC-SA

[zacontraption]

When I was an undergrad 7 years ago (not MIT), I watched Erik's MIT OCW lectures to supplement my in-person CS courses. The quality of the education in these lectures is tremendous.

[ParthPatel-vjzv]

0:00 intro, priority queue interface
3:08 set AVL data-structure
08:18 priority queue sort
10:10 comparing priority queue sorting algos based on set AVL, array & sorted array
14:24 complete binary tree
19:47 implicit data structure
24:49 binary heap Q
31:00 insert(x), max_heapify_up(i)
37:10 delete_max(), max_heapify_down(i)
44:25 in-place, O(n) build time

[fgfanta]

Quite amazing how the teachers manage to improve over the lectures uploaded in 2013, that were gold already.

[ArunKumar-utrq]

personal rewatch reference - 12:00 (rewatch why selection sort for unsorted dynamic array and insertion sort for sorted dynamic array)

[rocketman]

this was an amazing lecture; I learned a lot thank you.

[manguy]

This literally made the whole picture easier. I was being lazy at learning binary heaps and heap sort because they seemed daunting. But this lecture made everything make sense. Wish me luck with interviews :P

[thanirmalai]

The best lecturer i have ever seen in my life

[djn]

Word, I didn’t realize the completeness of the tree was what allows us to store it in an array. 18:48

[zchelseal]

Is my understanding correct of why we prefer to use an array over the pointers approach?
Since our implementation of insert, delete (and by extension, build) all comes down to insert_last or delete_last (with a bunch of value-swapping), each of which an array can support in constant time, it makes the pointer implementation less desirable because at each node we would need to store both a value and a pointer, which would effectively make our memory allocation double that of an array.
(are there any other benefits that I missed?)

[SalesforceUSA]

I don't know why YouTube recommended this to me, but I stayed for the whole lecture.,

[shymaaarafat]

For the implicit array presentation, would there be any problem if I made it 2D array with var size raws(one raw for each tree level, like a 90 angle triangle)?
-It's the same storage
-easier to visualize under any traversal
-if the tree is not complete, it would be easier to make it more dynamic (less shifts)
-I don't care about the heap property, I mean in the specific problem I'm thinking of internal nodes (non leaves) are just a function from real data at the leaves
-I also don't care very much about the time as long as the path length keeps logarithmic and doesn't increase with it
-So, even if the tree is not complete I'm still adding an extra space < 2N pointers
for X leaves
2^i < X < 2^(i+1)
If I had to reserve an extra space to reach full tree (I don't think I do, unless I went down to the memory blocks level to make the whole array in adjacent blocks)
-Anyways, if I had to reserve 2^(i+2) {2^(i+1) for leaves and 2^(i+1) for internal nodes, upper rows in my design}
Then extra space is 2^(i+2)-2X ....[2]
While extra space, assuming both fields have the same size, for pointer case is 2X
-And we have from [1] :
2^(i+1)<2X<2^(i+2)
Hence in [2], since we're subtracting more then the half
We are sure that we saved space
.
Sorry for getting into too much details, but is something wrong, anything I missed in my design?