1 of 15

Heaps

2 of 15

Binary Min-Heap

A binary heap is a binary tree where

  • Every node is less than or equal to all of its children
  • The tree is complete such that every level of the tree is completely filled, except for the bottom row which is filled from left to right

17

19

36

7

2

3

1

25

100

To insert an element into a binary heap, we percolate the element up

  1. Put the element in the new location
  2. If parent is larger, then swap with parent
  3. Keep swapping until either parent is smaller, or reached root

3 of 15

Problem 4

Try (a)

4 of 15

Problem 4a

Insert 10, 7, 15, 17, 12, 20, 6, 32 into a min heap.

–

​

​

​

​

​

​

​

​

​

5 of 15

Problem 4a

Insert 10, 7, 15, 17, 12, 20, 6, 32 into a min heap.

–

​

​

​

​

​

​

​

​

​

10

insert(10)

  • Already in its place

10

6 of 15

Problem 4a

Insert 10, 7, 15, 17, 12, 20, 6, 32 into a min heap.

–

10

​

​

​

​

​

​

​

​

7

10

insert(7)

  • percolateUp(7)

7

7 of 15

Problem 4a

Insert 10, 7, 15, 17, 12, 20, 6, 32 into a min heap.

–

7

10

​

​

​

​

​

​

​

10

7

insert(7)

  • percolateUp(7)
  • Everything in its place

8 of 15

Problem 4a

Insert 10, 7, 15, 17, 12, 20, 6, 32 into a min heap.

​

–

7

10

15

​

​

​

​

​

​

10

15

7

insert(15)

  • Already in its place

9 of 15

Problem 4a

Insert 10, 7, 15, 17, 12, 20, 6, 32 into a min heap.

–

7

10

15

​

​

​

​

​

​

10

15

7

17

insert(17)

  • Already in its place

17

10 of 15

Problem 4a

Insert 10, 7, 15, 17, 12, 20, 6, 32 into a min heap.

–

7

10

15

17

​

​

​

​

​

10

15

7

17

12

insert(12)

  • Already in its place

12

11 of 15

Problem 4a

Insert 10, 7, 15, 17, 12, 20, 6, 32 into a min heap.

–

12

​

​

​

​

10

15

7

17

12

20

insert(20)

  • Already in its place

7

10

15

17

20

12 of 15

Problem 4a

Insert 10, 7, 15, 17, 12, 20, 6, 32 into a min heap.

–

​

​

​

6

insert(6)

  • percolateUp(6)

10

15

7

17

12

20

12

20

7

10

15

17

6

13 of 15

Problem 4a

Insert 10, 7, 15, 17, 12, 20, 6, 32 into a min heap.

–

15

​

​

15

insert(6)

  • percolateUp(6)

10

6

7

17

12

20

12

20

7

10

6

17

  • percolateUp(6)

14 of 15

Problem 4a

Insert 10, 7, 15, 17, 12, 20, 6, 32 into a min heap.

–

15

​

​

15

insert(6)

  • percolateUp(6)

10

7

6

17

12

20

12

20

6

10

7

17

  • percolateUp(6)
  • Everything in its place

15 of 15

Problem 4a

Insert 10, 7, 15, 17, 12, 20, 6, 32 into a min heap.

–

15

​

​

15

insert(32)

  • Already in its place

10

7

6

17

12

20

12

20

6

10

7

17

32

32