1.) Prove (or disprove) that if a BST is full, the inorder predecessor of an internal node is a leaf node. 2.) The maximum (or minimum) item in a heap is always located at its root. A sorting...

1.) Prove (or disprove) that if a BST is full, the inorder predecessor of an internal node is a leaf node.


2.) The maximum (or minimum) item in a heap is always located at its root. A sorting algorithm called Heap Sort uses this data structure to sort a list in
O(n
log
n)
time. How would this algorithm look like? Provide a pseudocode, flowchart, or actual code and show it is able to achieve this time complexity.  What is the
cost to achieve this faster time complexity?

3.)Load factor (α) is defined as the ratio of the number of elements (n) to the number of slots (m) in a given hash table:

α=n/m

Does the load factor imply anything about the number of collisions expected? What does a load factor greater than 1 imply?