Heapify will work with lists of tuples such that the first element of each tuple is the value, so use (distance, node) instead

To make a heap based on the first (0 index) element:

import heapq
heapq.heapify(A)

If you want to make the heap based on a different element, you'll have to make a wrapper class and define the __cmp__() method.

The problem is that myList is a tuple. Try this:

myList = [('a', 1), ('b', 2)]
heapify(myList)

As per @JimMischel's comment, place your tuples in a tuple with the priority as the first element. Then use heapq:

import heapq

list = [('a', 2), ('b', 1), ('c', 0), ('d', 1)]
heap_elts = [(item[1], item) for item in list]
heapq.heapify(heap_elts)  # you specifically asked about heapify, here it is!
while len(heap_elts) > 0:
    print(heapq.heappop(heap_elts)[1])    # element 1 is the original tuple

produces:

('c', 0)
('b', 1)
('d', 1)
('a', 2)

The error is happening because tuples are compared lexicographically. If two distances are the same, the comparison moves on to the Vertex objects themselves.

Two solutions readily come to mind. The first is simply to add a unique index to the tuple before the Vertex but after the distance. This is easy, and would work even if you didn't have access to the Vertex class:

unvisitedQueue = [(v.getDistance(), i, v) for i, v in enumerate(G) if v not in visited]

The second option is to modify Vertex to have a __lt__ magic method:

def __lt__(self, other):
    return self.getDistance() < other.getDistance()

This is nice because you can heapify more directly now:

unvisitedQueue = [v for v in G if v not in visited]

You can simply use the tuple as they are. The Python documentation explicitly makes note of such as usage:

Heap elements can be tuples. This is useful for assigning comparison values (such as task priorities) alongside the main record being tracked:

>>> h = []
>>> heappush(h, (5, 'write code'))
>>> heappush(h, (7, 'release product'))
>>> heappush(h, (1, 'write spec'))
>>> heappush(h, (3, 'create tests'))
>>> heappop(h)
(1, 'write spec')

Simply push the tuples to the heap, and pop them off when needed:

>>> from heapq import heappush, heappop
>>> 
>>> heap = []
>>> tuples = [(5,"foo",True),(2,"bar", False),(8,"foobar",True)] 
>>> 
>>> for tup in tuples:
...     heappush(heap, tup)
... 
>>> heappop(heap)
(2, 'bar', False)

Because the implementation for heap uses default sorting for tuples

while pos > startpos:
    ...
    if newitem < parent:
        ...
    ...
...

and Python sorts tuples element-wise, ensure the objects by which you want the tuples to be sorted come first.

You could append each element into the heap in whatever order you want. Heap recognizes them as (num1, num2) where num1 is used for ranking. Below is an option:

hp = []
for e in x:
    hp.append((e[1], e[0]))

heapq.heapify(hp)
new = []
while hp:
    y = heapq.heappop(hp)
    new.append([y[1], y[0]])
print(new)

The array new will have the order you want.