Determining if a list of numbers is in heap order, Python 3.2

Question

I just discovered heap (in real life and in Python) and now I'm trying to determine if a certain list of random numbers is in heap order.
Problem is I'm not sure myself if I actually understand "heap" in practice even though I believe the definition provided makes sense.

I found some practice problems that should help you write heap psuedo code. This is the problem and below it is my attempt at solving it:

Write a function that checks whether a list of numbers is a heap or not:

Given a list, it returns True if the numbers are in a heap order, and False if the numbers are not and have the programme return and print the answer.

Example:

• returns True: the following list is in heap order: [0,1, 10, 2, 3, 11, 12, 4, 5, 19, 15]
• returns False the following list is not in heap order: [0, 1, 10, 2, 15, 11, 12, 4, 5, 19, 3]

Then there were 2 lists with a bunch of random numbers from 1 - 100 thrown in there, and some repeat.

    def heap_or(A):
      n = len(A)
      for i in range(n):
        start = (len(A) - 2) / 2
        while start >= 0:
          siftDown(A, start, len(A) - 1)
          start -= 1:
             return 'True'
        else:
             return 'False'

    def siftDown(A, start, end):
    root = start
    while root * 2 + 1 <= end:
        number = root * 2 + 1
        if number + 1 <= end and A[number] < A[number + 1]:
            number += 1
        if number <= end and A[root] < A[number]:
            A[root], A[number] = A[number], A[root]
            root = number
        else:
            return

     print 

Can somebody please give me a hand? Because I'm not really sure if I'm defining heap correctly the code is giving me a hard time as well!

Answer 1

The heap property (for a max heap) is that each node should be greater than or equal to its parent. The parent of element i in a binary heap stored in an array is element (i - 1) // 2:

def is_heap(A):
    return all(A[i] >= A[(i - 1) // 2] for i in range(1, len(A)))

Obviously because the heap is stored in array we don't need to check the shape.