- A Binary Heap Is Conceptually Thought Of As A Tree With Two Special Properties 1 A Shape Property The Binary Heap Is 1 (196.67 KiB) Viewed 17 times
A binary heap is conceptually thought of as a tree with two special properties: 1. A shape property - the binary heap is an almost complete binary tree (where each level of the tree has the maximum number of nodes possible, with the exception of the lowest level which is filled with nodes from left to right. 2. An order property - a partial ordering over the nodes where the key at every parent node is less than or equal to both of its children. An effective way to implement a binary heap is to use a Python list as the underlying data structure. An advantage of this approach is that for any value in the list (at index i) we can very quickly compute the index of both of its children (i * 2 and i * 2 + 1) and its parent (i // 2). An example is illustrated below: parent 0 1 2 3 4 5 6 7 8 9 10 11 children Define a function called is_binary_heap (a_list) which takes a Python list as a parameter. The value stored in index position 0 is 0 and is ignored. The values stored in all other index positions of the list are considered to be nodes in the heap. The function should return True if the Python list represents a valid binary heap as defined at the beginning of this question, and False otherwise. You can assume that the parameter list is not empty. For example: Test Result print (is_binary_heap ( [0, 6, 7, 8, 9, 22, 45, 12, 16, 27, 36])) True print (is_binary_heap ( [0, 6])) True print (is_binary_heap ( [0, 6, 7, 50, 2])) False