Building a heap from scratch

A heap is a data structure that can be represented as an array the ordering of elements in the array represent the structure of the heap let's take an example [100, 19, 36, 17, 3, 25, 1, 2, 7]

Given a node at index i, its children are at indices 2i + 1 and 2i + 2 we can see this in the example, 100 is at index 0 and its children are at 1 and 2.

36 is at index 2, and its children are at 5 and 6.

How can we verify that this is a heap? and how do we ensure this remains a heap as we add and remove elements?

We can effectively bubble up values that don't satisfy the heap property simply put, for each value in the array/heap, if the child is greater than the parent, then swap it upwards until it is smaller than its parent

One class of problem is finding the top k elements of some collection of elements. We can solve this by building a heap, taking the first element from that heap, then re-creating that heap etc. this would mean the complexity for k elements is n for creation of the heap and k * log(n) for getting the result. As once we remove the top element we have to recreate the heap. We can do this in log(n) time by taking the children of the root node, getting the smaller one, and traversing down the tree until it is less than the current node, then attaching it. Whatever we replace would then have to be bubbled down further.