Final answer:
A max heap is constructed by placing elements in a binary tree and heapifying from the bottom up. Inserting a new node into a max heap involves adding the element to the end and swapping it with parent nodes until the heap property is restored.
Step-by-step explanation:
Constructing a Max Heap
To construct a max heap from the array [1,5,6,8,12,14,16], follow these steps:
Start by placing the elements into a binary tree, following the order of the array from left to right and top to bottom.
Transform the binary tree into a max heap by 'heapifying' the tree, starting from the bottom non-leaf nodes and working up to the root. Ensure that each parent node is larger than its children.
Once completed, the max heap will have the largest element (16) as the root, and every other element properly placed to maintain the max heap properties.
Inserting a Node into a Max Heap
Starting with the max heap [50,30,20,15,10,8,16], after inserting a new node with the value 60, follow these steps:
Add the new element at the end of the heap, preserving the complete binary tree structure.
Since 60 is larger than its parent, swap the new element with its parent nodes until the max heap property is restored.
The new heap should now have 60 as the root, followed by a series of swaps to maintain the heap structure.