14
A heap, also known as a priority-queue, is an abstract data type. Conceptually, it's a binary tree where the children of every node are smaller than or equal to the node itself. (Assuming it's a max-heap.) When an element is pushed or popped, the heap rearranges itself so the the biggest element is the next to be popped. It can easily be implemented as a tree or as an array.
Your challenge, should you choose to accept it, is to determine if an array is a valid heap. An array is in heap form if every element's children are smaller than or equal to the element itself. Take the following array as an example:
[90, 15, 10, 7, 12, 2]
Really, this is a binary tree arranged in the form of an array. This is because every element has children. 90 has two children, 15 and 10.
15, 10,
[(90), 7, 12, 2]
15 also has children, 7 and 12:
7, 12,
[90, (15), 10, 2]
10 has children:
2
[90, 15, (10), 7, 12, ]
and the next element would also be a child of 10, except that there isn't room. 7, 12 and 2 would all also have children if the array was long enough. Here is another example of a heap:
[16, 14, 10, 8, 7, 9, 3, 2, 4, 1]
And here is a visualization of the tree the previous array makes:
Just in case this isn't clear enough, here is the explicit formula to get the children of the i'th element
//0-indexing:
child1 = (i * 2) + 1
child2 = (i * 2) + 2
//1-indexing:
child1 = (i * 2)
child2 = (i * 2) + 1
You must take an non-empty array as input and output a truthy value if the array is in heap order, and a falsy value otherwise. This can be a 0-indexed heap, or a 1-indexed heap as long as you specify which format your program/function expects. You may assume that all arrays will only contain positive integers. You may not use any heap-builtins. This includes, but is not limited to
- Functions that determine if an array is in heap-form
- Functions that convert an array into a heap or into heap-form
- Functions that take an array as input and return a heap data-structure
You can use this python script to verify if an array is in heap-form or not (0 indexed):
def is_heap(l):
for head in range(0, len(l)):
c1, c2 = head * 2 + 1, head * 2 + 2
if c1 < len(l) and l[head] < l[c1]:
return False
if c2 < len(l) and l[head] < l[c2]:
return False
return True
Test IO:
All of these inputs should return True:
[90, 15, 10, 7, 12, 2]
[93, 15, 87, 7, 15, 5]
[16, 14, 10, 8, 7, 9, 3, 2, 4, 1]
[10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
[100, 19, 36, 17, 3, 25, 1, 2, 7]
[5, 5, 5, 5, 5, 5, 5, 5]
And all of these inputs should return False:
[4, 5, 5, 5, 5, 5, 5, 5]
[90, 15, 10, 7, 12, 11]
[1, 2, 3, 4, 5]
[4, 8, 15, 16, 23, 42]
[2, 1, 3]
As usual, this is code-golf, so standard loopholes apply and the shortest answer in bytes wins!
Related – James – 2016-07-10T22:50:35.177
Is it correct that if there are repeated elements, it may be impossible to form a heap according to this definition? – feersum – 2016-07-10T23:00:26.583
@feersum What about
[3, 2, 1, 1]
? – Neil – 2016-07-10T23:04:53.943@feersum That's a great point, I hadn't thought of that. I updated the description of a heap and added some example with duplicate elements. Thank you! – James – 2016-07-10T23:07:02.460
5A heap is not also known as a priority queue. A priority queue is abstract data type. A heap is data structure sometimes used to implement a priority queue (The heap itself is implemented on top of even more fundermental data structures, but that is beside the point). Priority queues can be implemented on top of other data structures -- like linked lists. – Lyndon White – 2016-07-11T11:41:50.250