8. Binary Heaps

[@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.

[@aeroartz4080]

is it useful to know data structures and algorithms? how has knowing this stuff been helpful so far

[@fran150695]

​@@aeroartz4080 I am 2 months late, but I think this answer might be useful to some other people that might see it later. As a person who has been working in the industry for a couple of years. I can say that knowing Data structures and algorithms has been really useful to me. Why? I believe that this is a 2 part answer. 1. Knowing the different kinds of data structures and what makes them better for specific tasks will allow you to know what to choose for what job. Many times I have found that If I just relegated to use the standard "array" I would need to spend a much larger time coding my solutions to the tasks, because the Array is not optimized to the problem to solve. (This would also mean a significant slow on the speed of the code, but that is usually not a problem) 2. The whole "algorithms" part has a very very useful yet obscure usage on the industry. 99% of the time you will never be implementing the algorithms yourself. You can just call a library and they do it for you, but what you learn in these areas is to understand the code and know what is happening. This really helps to both know what libraries to use as well as to make your code efficient and have a much easier time when you need to implement your own algorithms.

[@makelearningeasy111]

Indeed

[@SpeaksYourWord]

@@fran150695 Thank you. This eases the pain a bit 😆

[@ParthPatel-vj2zv]

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.

[@thanirmalai]

The best lecturer i have ever seen in my life

[@ArunKumar-ut4rq]

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

[@manguy2011]

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

[@MehbubulHasanAlQuvi]

OMG OMG OMG! Much Anticipated! Gold!

[@djn138]

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

[@rocketman3770]

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

[@shymaaarafat1342]

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) .....[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)

[@shymaaarafat1342]

Likes are not welcomed, only answers

[@shymaaarafat1342]

@Andriy Dmytriyev And you wake up after 4 months to reply to such an old comment?! . No a 2d array of previously known size doesn't involve any pointers thank you for your polite words

[@shymaaarafat1342]

That was a very rude person, a deliberately malicious reply . What I meant is that I just used the features of some Programming languages that makes you able to address a 2d array to make the index formula more easier to calculate, but the main idea is exactly as it is explained here a contiguous array in memory that is eventually will be indexed as a vector or 1D array

[@anonymitynone6957]

I think you mean for a 2d array A,len(A[0])=1,len(A[1])=2...len(A[i])=2^i at first as "like a 90 angle triangle" describes,(I can't clearly understand what your design means),but why it would be easier to make it more dynamic if the tree is not complete

[@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?)

[@paulluckner411]

You need to know that CPUs are more efficient at working with contiguous memory compared to distinct small heap allocated chunks. You might want to do some online searches on cache lines, cache-friendliness, pointer chasing. This is also the reason why std::vector is recommended to be the default data structure in C++.

[@SalesforceUSA]

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

[@NavinY5]

Day 12 present

[@jurgenblick5491]

I like this