Question

True False

		The enqueue and dequeue operations in a priority queue take O(lg n) time, while linked list and array implementations take O(1) time.
		A binary heap is a (nearly) complete binary tree.
		Heaps usually use a linked node structure for implementation.
		When implementing heaps as arrays, you can leave a blank space at the front. If you do, the parent of a node at index i can be found at index floor(i/2).
		When implementing heaps as arrays, if you don't leave a space at the front, you can find the children of the node at index i at 2i and 2i+1.
		The heap order property states that each node must contain a value greater than its left child and less than its right child.
		Insertion in a heap is done by adding at the end of the array and "percolating up".
		The average case for insertion in a heap is O(lg n). The worst case is O(n).
		Deletion in a heap requires removing the root item and shifting all other items over one space.
		Building a heap by adding values one at a time is an O(n) operation. Building a heap "all at once" with the heapify() method (called buildHeap() in the textbook) is O(n lg n).

Answer 1

1)The enqueue and dequeue operations in a priority queue take O(lg n) time, while linked list and array implementations take O(1) time.

It is true that enqueue and dequeue operation on a priority queue is implemented in O(log n) time.In linked list implementation,it is arranged in order and hence dequeue operation is performed in O(1) time while in equeue opration we will have to traverse the list,so it takes O(n) time.

Therefore,This statement is overall False.

2) A binary heap is a (nearly) complete binary tree.

Def: - A nearly complete binary tree of height h is a binary tree of height h in which

a) There are 2d nodes at depth d for d = 1,2,...,h−1,

b) The nodes at depth h are as far left as possible.

This defintion holds good for max-heap or simply binary heap,

Therefore, this statement is True.

3) Heaps usually use a linked node structure for implementation.

Heaps are generally implemented as arrays.

Therefore, this statement is false.

4) When implementing heaps as arrays, you can leave a blank space at the front. If you do, the parent of a node at  index i can be found at index floor(i/2).

This statement is true.

5) When implementing heaps as arrays, if you don't leave a space at the front, you can find the children of the node at index i at 2i and 2i+1.

This statement is False.

6) The heap order property states that each node must contain a value greater than its left child and less than its right child.

This statement is false.

Because, for being a heap,root must be greater or smaller than both the childs.

7) Insertion in a heap is done by adding at the end of the array and "percolating up".

this is True.

Because,we add at the end and perform heapify process in which values percolates upwards if it is not its correct position.

8). The average case for insertion in a heap is O(lg n). The worst case is O(n).

It is False.

Because,in average case insertion in heap takes O(1) time. And in worst case it takes O(logn) time.

9)  Deletion in a heap requires removing the root item and shifting all other items over one space.

This is false.

Because, All items may not get shifted by one position.

10)  Building a heap by adding values one at a time is an O(n) operation. Building a heap "all at once" with the heapify() method (called buildHeap() in the textbook) is O(n lg n).

This is false.

Because adding a value takes O(logn) time(Due to heapify process).while there are n values and each value takes logn time so overall it will take O(nlogn) time.