Every edge weighs 0 or 1, so a heap is overkill. Use a deque: a vertex reached over a 0 edge is as close as the vertex it came from and goes to the front. One reached over a 1 edge is one further and goes to the back. The deque then always pops vertices in order of distance, which is exactly what Dijkstra's heap provides, at O(V + E).
0-1 BFS from 0.
Pop 0 from the front at distance 0. Deque now empty. Look at its edges.
Pop 0 at 0.
Edge 0 to 1 weighs 1: 0 + 1 = 1 against 1's current infinity. Shorter, so 1 becomes 1 and joins the back of the deque: one step further than 0. Deque now 1.
Edge 0 to 1: 1 against infinity. Pushed.
Edge 0 to 2 weighs 0: 0 + 0 = 0 against 2's current infinity. Shorter, so 2 becomes 0 and joins the front of the deque: it is as close as 0. Deque now 2 1.
Edge 0 to 2: 0 against infinity. Pushed.
Pop 2 from the front at distance 0. Deque now 1. Look at its edges.
Pop 2 at 0.
Edge 2 to 0 weighs 0: 0 + 0 = 0 against 0's current 0. Not shorter, so 0 keeps 0 and is not pushed.
Edge 2 to 0: 0 against 0. No change.
Edge 2 to 3 weighs 1: 0 + 1 = 1 against 3's current infinity. Shorter, so 3 becomes 1 and joins the back of the deque: one step further than 2. Deque now 1 3.
Edge 2 to 3: 1 against infinity. Pushed.
Edge 2 to 4 weighs 1: 0 + 1 = 1 against 4's current infinity. Shorter, so 4 becomes 1 and joins the back of the deque: one step further than 2. Deque now 1 3 4.
Edge 2 to 4: 1 against infinity. Pushed.
Pop 1 from the front at distance 1. Deque now 3 4. Look at its edges.
Pop 1 at 1.
Edge 1 to 0 weighs 1: 1 + 1 = 2 against 0's current 0. Not shorter, so 0 keeps 0 and is not pushed.
Edge 1 to 0: 2 against 0. No change.
Edge 1 to 3 weighs 0: 1 + 0 = 1 against 3's current 1. Not shorter, so 3 keeps 1 and is not pushed.
Edge 1 to 3: 1 against 1. No change.
Pop 3 from the front at distance 1. Deque now 4. Look at its edges.
Pop 3 at 1.
Edge 3 to 1 weighs 0: 1 + 0 = 1 against 1's current 1. Not shorter, so 1 keeps 1 and is not pushed.
Edge 3 to 1: 1 against 1. No change.
Edge 3 to 2 weighs 1: 1 + 1 = 2 against 2's current 0. Not shorter, so 2 keeps 0 and is not pushed.
Edge 3 to 2: 2 against 0. No change.
Edge 3 to 4 weighs 1: 1 + 1 = 2 against 4's current 1. Not shorter, so 4 keeps 1 and is not pushed.
Edge 3 to 4: 2 against 1. No change.
Pop 4 from the front at distance 1. Deque now empty. Look at its edges.
Pop 4 at 1.
Edge 4 to 2 weighs 1: 1 + 1 = 2 against 2's current 0. Not shorter, so 2 keeps 0 and is not pushed.
Edge 4 to 2: 2 against 0. No change.
Edge 4 to 3 weighs 1: 1 + 1 = 2 against 3's current 1. Not shorter, so 3 keeps 1 and is not pushed.
Edge 4 to 3: 2 against 1. No change.
Edge 4 to 5 weighs 0: 1 + 0 = 1 against 5's current infinity. Shorter, so 5 becomes 1 and joins the front of the deque: it is as close as 4. Deque now 5.
Edge 4 to 5: 1 against infinity. Pushed.
Pop 5 from the front at distance 1. Deque now empty. Look at its edges.
Pop 5 at 1.
Edge 5 to 4 weighs 0: 1 + 0 = 1 against 4's current 1. Not shorter, so 4 keeps 1 and is not pushed.
Edge 5 to 4: 1 against 1. No change.
Distances from 0: 0: 0, 1: 1, 2: 0, 3: 1, 4: 1, 5: 1. 6 pops and 14 edge checks, O(V + E): the deque stood in for the heap because only two distances, d and d + 1, are ever waiting at once.
0-1 BFS finished. vertex 0 at 0, vertex 1 at 1, vertex 2 at 0, vertex 3 at 1, vertex 4 at 1, vertex 5 at 1.