Implement A Binary Heap - An Efficient Implementation of The Priority Queue ADT (Abstract Data Type)
Вставка
- Опубліковано 30 січ 2019
- Free 5-Day Mini-Course: backtobackswe.com
Try Our Full Platform: backtobackswe.com/pricing
📹 Intuitive Video Explanations
🏃 Run Code As You Learn
💾 Save Progress
❓New Unseen Questions
🔎 Get All Solutions
Question: Implement a binary heap (a complete binary tree which satisfies the heap ordering property). It can be either a min or a max heap.
Video On Heap Sort: • Investigating Heap Sor...
Priority Queue ADT (Abstract Data Type)
The ADT's Fundamental API
isEmpty()
insertWithPriority()
pullHighestPriorityElement()
peek() (which is basically findMax() or findMin()) is O(1) in time complexity and this is crucial.
A heap is one maximally efficient implementation of a priority queue.
We can have:
-) a min heap: min element can be peeked in constant time.
-) or a max heap: max element can be peeked in constant time.
The name of the heap indicates what we can peek in O(1) time.
It does not matter how we implement this as long as we support the expected behaviors of the ADT thus giving our caller what they want from our heap data structure.
A binary heap is a complete binary tree with a total ordering property hence making it a heap with O(1) peek time to the min or max element.
We can implement the heap with actual nodes or we can just use an array and use arithmetic to know who is a parent or left or right child of a specific index.
Insertion into a binary heap:
We insert the item to the "end" of the complete binary tree (bottom right of the tree).
We "bubble up" the item to restore the heap. We keep bubbling up while there is a parent to compare against and that parent is greater than (in the case of a min heap) or less than (in the case of a max heap) the item. In those cases, the item we are bubbling up dominates its parent.
Removal from a binary heap:
We give the caller the item at the top of the heap and place the item at the "end" of the heap at the very "top".
We then "bubble the item down" to restore the heap property.
Min Heap: We keep swapping the value with the smallest child if the smallest child is less than the value we are bubbling down.
Max Heap: We keep swapping the value with the largest child if the largest child is greater than the value we are bubbling down.
In this manner, we restore the heap ordering property.
The critical thing is that we can have O(1) knowledge of the min or max of a set of data, whenever you see a problem dealing with sizes think of a min or max heap.
++++++++++++++++++++++++++++++++++++++++++++++++++
HackerRank: / @hackerrankofficial
Tuschar Roy: / tusharroy2525
GeeksForGeeks: / @geeksforgeeksvideos
Jarvis Johnson: / vsympathyv
Success In Tech: / @successintech - Наука та технологія
Table of Contents:
Plugging The Channel 0:00 - 0:36
The Problem Introduction 0:36 - 1:13
A Heap Is Not An ADT 1:13 - 1:43
The ADT Priority Queue 1:43 - 3:39
The Min and Max Heap 3:39 - 5:50
Insertions & Removals On A Min Heap 5:50 - 8:57
Our First Removal 8:57 - 11:16
Continue Insertions 11:16 - 13:20
Our Second Removal 13:20 - 15:21
Our Third Removal 15:21 - 15:54
Continue Insertions 15:54 - 17:47
Notice Our Heaps Contents 17:47 - 18:32
Time Complexity For Insertion & Removal 18:32 - 19:35
Wrap Up 19:35 - 20:00
The code is in the description fully commented for teaching purposes.
I don't see the code in the description or a link to it. Am I blind or is it gone?
The repository is deprecated - we only maintain backtobackswe.com now
@@BackToBackSWE So it's not free anymore?
where can i find c++ code... and I don't find any code in description
@@saffaura public class Solution {
/*
A min heap implementation
Array Form: [ 5, 7, 6, 10, 15, 17, 12 ]
Complete Binary Tree Form:
5
/ \
7 6
/ \ / \
10 15 17 12
Mappings:
Parent -> (childIndex - 1) / 2
Left Child -> 2 * parentIndex + 1
Right Child -> 2 * parentIndex + 2
*/
private static class MinHeap {
private int capacity = 5;
private int heap[];
private int size;
public MinHeap() {
heap = new int[capacity];
}
public boolean isEmpty() {
return size == 0;
}
public int peek() {
if (isEmpty()) {
throw new NoSuchElementException("Heap is empty.");
}
return heap[0];
}
public int remove() {
if (isEmpty()) {
throw new NoSuchElementException("Heap is empty.");
}
/*
-> Grab the min item. It is at index 0.
-> Move the last item in the heap to the "top" of the
heap at index 0.
-> Reduce size.
*/
int minItem = heap[0];
heap[0] = heap[size - 1];
size--;
/*
Restore the heap since it is very likely messed up now
by bubbling down the element we swapped up to index 0
*/
heapifyDown();
return minItem;
}
public void add(int itemToAdd) {
ensureExtraCapacity();
/*
-> Place the item at the bottom, far right, of the
conceptual binary heap structure
-> Increment size
*/
heap[size] = itemToAdd;
size++;
/*
Restore the heap since it is very likely messed up now
by bubbling up the element we just put in the last empty
position of the conceptual complete binary tree
*/
siftUp();
}
/***********************************
Heap restoration helpers
***********************************/
private void heapifyDown() {
/*
We will bubble down the item just swapped to the "top" of the heap
after a removal operation to restore the heap
*/
int index = 0;
/*
Since a binary heap is a complete binary tree, if we have no left child
then we have no right child. So we continue to bubble down as long as
there is a left child.
A non-existent left child immediately tells us that a right child does
not exist.
*/
while (hasLeftChild(index)) {
/*
By default assume that left child is smaller. If a right
child exists see if it can overtake the left child by
being smaller
*/
int smallerChildIndex = getLeftChildIndex(index);
if (hasRightChild(index) && rightChild(index) < leftChild(index)) {
smallerChildIndex = getRightChildIndex(index);
}
/*
If the item we are sitting on is < the smaller child then
nothing needs to happen & sifting down is finished.
But if the smaller child is smaller than the node we are
holding, we should swap and continue sifting down.
*/
if (heap[index] < heap[smallerChildIndex]) {
break;
} else {
swap(index, smallerChildIndex);
}
// Move to the node we just swapped down
index = smallerChildIndex;
}
}
// Bubble up the item we inserted at the "end" of the heap
private void siftUp() {
/*
We will bubble up the item just inserted into to the "bottom"
of the heap after an insert operation. It will be at the last index
so index 'size' - 1
*/
int index = size - 1;
/*
While the item has a parent and the item beats its parent in
smallness, bubble this item up.
*/
while (hasParent(index) && heap[index] < parent(index)) {
swap(getParentIndex(index), index);
index = getParentIndex(index);
}
}
/************************************************
Helpers to access our array easily, perform
rudimentary operations, and manipulate capacity
************************************************/
private void swap(int indexOne, int indexTwo) {
int temp = heap[indexOne];
heap[indexOne] = heap[indexTwo];
heap[indexTwo] = temp;
}
// If heap is full then double capacity
private void ensureExtraCapacity() {
if (size == capacity) {
heap = Arrays.copyOf(heap, capacity * 2);
capacity *= 2;
}
}
private int getLeftChildIndex(int parentIndex) {
return 2 * parentIndex + 1;
}
private int getRightChildIndex(int parentIndex) {
return 2 * parentIndex + 2;
}
private int getParentIndex(int childIndex) {
return (childIndex - 1) / 2;
}
private boolean hasLeftChild(int index) {
return getLeftChildIndex(index) < size;
}
private boolean hasRightChild(int index) {
return getRightChildIndex(index) < size;
}
private boolean hasParent(int index) {
return index != 0 && getParentIndex(index) >= 0;
}
private int leftChild(int index) {
return heap[getLeftChildIndex(index)];
}
private int rightChild(int index) {
return heap[getRightChildIndex(index)];
}
private int parent(int index) {
return heap[getParentIndex(index)];
}
}
}
This man explains better than my prof who has a PhD in Comp Sci lmao One of the best channels to understand Data Structures!
hey
@@BackToBackSWE hey have one question. What would be time complexity (both iterative and recursive) for verifying/building a general K-ary max heap (not just binary but for ternary and so forth)?
If not the best
well, you do realise you are visiting this topic not the first time?
Well getting a PhD doesn't really correlate with how well you can explain a simple-data structure
i really appreciate the fact you edit out the insane amount of erasing and rewriting youre doing in all of these. each of these videos must take so long to record and edit O_O thanks mate
hahahahhaha, thanks for noticing the details. Yeah each video takes from 4-6 hours from shooting to editing.
This channel is by far the best at breaking down and explaining DSA concepts that I've ever seen (including university). Thanks for your awesome work!
sure
I admire your dedication and treasure it a lot! It is an honour to have someone as skilled as you taking the time to explain these concepts for beginners like us!!!
haha im not that skilled
The way he explains, just goes into the mind..
ye
you are an increadible human being for puttin this content out there.
One of the best explanations I've seen for this topic, is complete, clear, with graphics, and examples. Thank you so much.
Very helpful! I feel like I’m in an actual lecture, but with an awesome instructor. Thanks for the video!
thanks and thanks
Thank you for the awesome explanation. Looking forward to more of your tutorial videos
sure
Omg, this video was posted 5 years back and is still the best video I've ever seen. Your explanation makes it so simple! Glad I found your channel.. it's a gem 💎❤
this channel is the reason i'll pass my data structures class )': thanks so much man please keep making these videos!! you really explain stuff so in-depth.
Nice, sure, workin' on it
Absolutely love the explanations of the fundamental building blocks of the more complex stuff! Much gratitude.
literally you explain better than any teacher I've ever had, keep it up, greetings from Colombia
The best explanation of heap I could found. Short and clear
This is literally a legendary video lol. I am learning BST and Heap in my data strucutres class and i understand majority of the BST stuff, but the heap was like, easy to understand but weird as hell to understand that its no longer an ADT etc. You did a great job explaining all this.
nice
Love your enthusiasm in this tutorial!
You are a legend. This channel is awesome for quick review and for first attempts. Thanks for all the forethought and effort put into your videos.
thx - wish u the best
legit one of the best channels on youtube. these are beautiful and my go-to interview studying (and my last-minute nerves studying). thank you for the wonderful content!
thanks wish u the best!
Man you don't know how much of a help you are for us! You always help me through, thank you so much you are the best.
Dude I swear you are the one making me pass my algo lecture! Your vids are helping me so much with every exercise
Absolutely amazing and thorough. Beautiful breakdown. Best explanation I have seen yet and could not have been better. Will check out your products and really hope your full courses and career services come in time for upcoming graduation and recruitment!
ye
2 minutes into the video, this guy answered questions I had to ask my professors for weeks to understand. You might not understand everything he is saying, but this is the same stuff that I'm being taught at a private, super expensive, well ranked engineering school. Thanks for the help!
Happy Holidays 🎉 Thank you for your kind words, MarkRosenthal! We'd love to offer you a 40% Off our exclusive lifetime membership just use the code CHEER40 - backtobackswe.com/checkout?plan=lifetime-legacy&discount_code=CHEER40
OMG you explain so clear! Thanks!
quality videos bro, I not only learn but I enjoy watching them too
Great video, as always! Nice job!
hola
Thank you so much for your videos that make algorithm so much easier to understand! Looking forward to more of them:)
sure
I like how he asks the question 'Do you see xxxx ?'. It just gives me a feeling that I'm actually sitting in front of him, and it makes me more engaged into the video.
Just found your channel, and smashed that subscribe button. Thank you so much for your content! It helps me and my GPA a lot.
Also, I can see your channel becoming the world's biggest resource of SWE in the future. Will support you through it all.
hey
Best explanation of heaps I've seen on here..thanks dude..so easy to follow.
sure.
First video of yours that I've seen. Excited to check out more. Thanks for the info!
Glad to hear that! Subscribe to our DSA course for some amazing content with a flat 30% discount b2bswe.co/3HhvIlV
This is "THE BEST CHANNEL" for SWE..... Love it
nobody:
ben: "we're missing one child, that's fine"
lol
You deserve a medal for all the work you do! and the best part you always reply to my comments! Keep enlightening us with your videos!😊😊
Thanks and no I don't, I had/have a mission and it has nothing to do with me. And yeah, I reply to everyone. And sure.
This video explains the remove so well.
The best explanation ever!
Thanks. Short and sweet review for my exam.
Thank you for the explanation, it’s easy to understand and very helpful!
Your videos are by far the best. Keep up the good work!
thanks
Thanks for the awesome explanation.
youtube takes time but is rewarding, keep the tempo going
lol ok
Amazing explanation!
Helped me implement this in minutes thanks to the video.
great
Glad I found your channel
You are so amazing... I think I'm best lucky for choosing this video tutorial among many others....
Amazing lecture, appreciate your efforts!!!
sure
DUDE you are killin it, thank you.
I'm fine and thanks
you are an excellent teacher! thankyou!!
This man smokes tricky concepts like it aint no thing! @B2BSWE, I like how you explain the concepts and don't just immediately jump into optimized code. I've seen videos like that before, where I guess the goal is to memorize a process and I walk away feeling unsure about what I "learned".
I got u, thx 4 watching
thnq so much man. it helped me a lot.Excellent explanation
I have to applaud you for this! Thank you, thank you! I love how u put it in Layman's term
one hell of a good explanation, keep doing what you're doing man, appreciate it
ok
Simplicity is quality of this channel.
Hello Sir!!!
I am from Myanmar student who is learning Software Engineering.
Your videos are so effective for me and you can explain very clearly.
Thanks for sharing your knowledge.
Sure
one of the best ds channels..great work
thanks thanks
Hands down to THE BEST CHANNEL
ye
Thank you for this amazing explanation.
sure
You are great teacher, what a clear explanation of each topic. Please post more learning videos of popular algorithms
thanks and ok
Man this vid is so rad! This is the best explanation I've seen yet. I've always wanted to implement compression with huffman coding and now this is is very clear. I never bothered to learn what log n complexity meant (altho I'm supposed to be a a dev) but now this is obvious. Like if you double the size of the elements in the binary tree you only have to go one step further to bubble up or down one element by comparing and swaping with parents/children hence it's log since it depends of the exponent value. Thank's.
thanks
Thanks a lot for this !!
Excellent video buddy really solidified the concept of a binary heap for me
sure
very detailed explaination
Best Explanation on Internet :)
thx
I had an onsite question that involved heaps... I didn't get the offer, and went on a berserk mode to understand where I went wrong. Your explanation is the clearest one I've seen. Thank you.
sure
You’re an awesome teacher!
helps a lot when im preparing for final thx!
sure
you just saved my semester
Thank you!!!!! You are so good, its hard not to recommend you
Thank you, glad you liked it 😀
Do check out backtobackswe.com/platform/content
and please recommend us to your family and friends 😀
thank you so much. actually i have implemented priority queue through linked list but then my prof said i have to implement through heaps. This is a very confusing topic but you actually made it so easy and understandable. ❤🌹
great
Best videos on data structure. Already said that, will say it again!!
thank you!
This dude is a straight boss I love your videos man 👍
Thanks Terry
awesome video! thank you for the clear and enthusiastic explanation:)
Happy Holidays 🎉 Thank you for your kind words, Rheya! We'd love to offer you a 40% Off our exclusive lifetime membership just use the code CHEER40 - backtobackswe.com/checkout?plan=lifetime-legacy&discount_code=CHEER40
I'm impress what a great explanation!
Glad it was helpful
Thank you. That was a nice explanation
thank you
amazing brother - nice and simple - keep going, i'll be checking here first!
Thank you, glad you liked it 😀
Do check out backtobackswe.com/platform/content
and please recommend us to your family and friends 😀
Thank you, its very helpful!
very clear explanation & examples
thanks null
Man . you are just the best . you are just doing something that a lot of people will appreciate you . your contexts are just perfect . I can't find tutorials about DS&ALG better than this channel .
I just don't understand your pause at the end of Videos :|)
Good luck ,you are truly amazing
Great work. ❤️❤️
I’m becoming a fan of yours...
very nice explanation
no im a fan of u
You're just great. Keep up good work!
thanks, hey
great explanation! thanks!
sure
9:44 heapify, such a cool word, I'm gona start using it
lol, I don't think it is a real word
@@BackToBackSWE in python standard library: heapq.heapify(x) is a thing. :)
@@neurochannels nice
Yeah...something out of a spell from Harry Potter
Super useful, thanks!
Sure
this is really good!..cheers
Happy Halloween 🎃 Cheers, fredflintstone! Cool username, You get some extraaa treats - 50% Off our exclusive lifetime membership use the code SPOOKY50 - backtobackswe.com/checkout?plan=lifetime-legacy&discount_code=SPOOKY50
Thanks John
sure
Thank you ! super helpful
sure
Good as always.
thanks
Clearly explained
Thank you so much!
This is great, thank you!
Please add captions...I'm taking notes of this concise and precise video, indeed a precious video. Thank you
thanks and ok
Wow, it's the best. Thank you
Happy Holidays 🎉 You're the best, selin! We'd love to offer you a 40% Off our exclusive lifetime membership just use the code CHEER40 - backtobackswe.com/checkout?plan=lifetime-legacy&discount_code=CHEER40
really helped ty
great
Great video!
Glad you enjoyed it
I’ve been looking for an instructor like you since i first started studying computer science almost seven years ago
Glad to hear that!
Subscribe to our DSA course with a flat 30% discount for some amazing content b2bswe.co/3HhvIlV
You are awesome, I am very grateful to you!
sure
Thank you!!!
thanks man .I hope i won't get stuck in any heap questions in interview again!
!!!!