Heap - Build Max Heap

Показать описание

In this video, I show you how the Build Max Heap algorithm works.

Рекомендации по теме

Комментарии

10 years later this is still really helpful!

garic

Watched at x2 and it immediately brought the algorithm back. Clearly you're amazing at presenting information. Thanks, mate!

ozzyfromspace

at 5:10, after i=1, your algorithm stops according to the code (for i=1 to 1). You have not explained how did you found out that the LEFT child of index i=1 does not align with the max_heap rules. You did it via visual inspection instead :(

chrise

Hi the algo starts from half of the length to 1, but when we reached at index 1, we destroyed the max heap property at index 2, but algo stops at 1. In the video we revisit the 2 index but algo is already stopped at index 1. Its unclear to me

varunsingh

Great, simple, and concise explanation. Thank you

brecoldyls

Thanks. Good video but just unclear on the last step once the root was swapped, how, programatically does it know to check the left subtree randomly? Also. What presentation software are you using? Thanks!

mrchedda

Yo! best video for explained how to structure maxheaps! Good job!

gamefreak

Your explanation is very easy to understand

theone

when i = 1 why did u max heapify again? its exit loop

TFShows

For those wondering how this algorithm works as it stops in the middle, you need to write a condition to check if maxHeap property is applied for the whole list everytime and repeat the process of heapify if it fails, here is an example
import java.util.Arrays;

public class MyClass {
static boolean maxHeapFormed = false;

public static void main(String args[]) {
int[] nums = {5, 12, 64, 1, 37, 90, 91, 97};

while(maxHeapFormed == false){
maxHeapify(nums);
checkMaxHeap(nums);
}

}

public static void checkMaxHeap(int[] nums){
int leftChild;
int rightChild;
for(int i = nums.length/2;i>=0;i--){
leftChild = 2*i+1;
rightChild = 2*i+2;
if(leftChild < nums.length && nums[leftChild] > nums[i]) return;
else if(rightChild < nums.length && nums[rightChild] > nums[i]) return;
}
maxHeapFormed = true;
}

public static void maxHeapify(int[] nums){
int length = nums.length;
for(int i = nums.length/2;i>=0;i--){
heapify(nums, i);
}
}
public static void heapify(int[] nums, int i){
int maxValue = i;
int leftChild = 2*i+1;
int rightChild = 2*i+2;
if(leftChild < nums.length && nums[leftChild] > nums[maxValue]) maxValue = leftChild;
if(rightChild < nums.length && nums[rightChild] > nums[maxValue]) maxValue = rightChild;

if(maxValue != i) swap(nums, maxValue, i);

}
public static void swap(int[] nums, int highest, int i){
int temp = nums[highest];
nums[highest] = nums[i];
nums[i] = temp;
}
}

chaitanyabalanagu

wish that someone explained like this in the lecture

maxkellerer

How do you go back and forth to check whether parent is greater than children? It's easy to swap with a pencil but how do you do in terms of coding? Thanks.

sahidulll

Nice I got it. Just wonder at the last step after the pointer i is at the root, do you then just check the whole heap a for broken properties or is there a more sophisticated approach to it? Thanks

nicklasnilsson

Hey i have a question on you... I understand why we needed to heapify node 2 after decrementing "i", but how do you explain it from algorithm point of view? is there something like post-for-loop check of rules or how?

MartinThePooh

Thank you - super clear and easy to follow. What software are you using to present your examples? I noticed you were able to erase a specific color and leave the rest of the board untouched.

chasemedia