Min heap - is a binary tree such that the data contained in each node (parent node) is less than the node's children. Max heap - is a binary tree such that the data contained in each node (parent node) is greater than the node's children. ____________________________________________________________________ Insert the following elements: Insert 4 1 6 2 8 7 7 2 6 3 Min heap: 1 / \ 2 6 / \ / \ 2 3 7 7 / \ / 4 6 8 Max heap: 8 / \ 6 7 / \ / \ 6 3 4 7 / \ / 1 2 2 ___________________________________________________________________ Remove elements from a min heap: 1 / \ 2 6 / \ / \ 2 3 7 7 / \ / 4 6 8 ------------------------------------------------- Remove = return 1. Tree now looks like this: 2 / \ 2 6 / \ / \ 4 3 7 7 / \ 8 6 ------------------------------------------------- Remove = return 2. Tree now looks like this: 2 / \ 3 6 / \ / \ 4 6 7 7 / 8 ------------------------------------------------- Remove = return 2. Tree now looks like this: 3 / \ 4 6 / \ / \ 8 6 7 7 ------------------------------------------------- Remove = return 3. Tree now looks like this: 4 / \ 6 6 / \ / 8 7 7 ------------------------------------------------- Remove = return 4. Tree now looks like this: 6 / \ 7 6 / \ 8 7 ------------------------------------------------- Remove = return 6. Tree now looks like this: 6 / \ 7 7 / 8 ------------------------------------------------- Remove = return 6. Tree now looks like this: 7 / \ 8 7 ------------------------------------------------- Remove = return 7. Tree now looks like this: 7 / 8 ------------------------------------------------- Remove = return 7. Tree now looks like this: 8 ------------------------------------------------- Remove = return 8 _______________________________________________________________ For those who looked this far: Here are a couple interesting things: 1 / \ 2 6 / \ / \ 2 3 7 7 / \ / 4 6 8 The list representation of this heap is: | 1 | 2 | 6 | 2 | 3 | 7 | 7 | 4 | 6 | 8 | This is made by going down each level going left to right. Using the list we can do interesting things: ex- left child = 2i + 1 right child = 2i + 2 parent = floor((i-1)/2) i represents the current node we are looking at. We start counting i from zero. For example to find the left child of the node 6: 6 is our 2nd node So: 2(2) + 1 = 5 The 5th element is our list is 7, which is the left child of the node 6.