Java ADT Tables, Priority Queues, Heaps, and Collections Framework

What is an ADT table?

An ADT table, or dictionary, uses a search key to identify its items, which are records containing several pieces of data.

List the operations of the ADT table.

1. Create an empty table 2. Determine whether a table is empty 3. Determine the number of items in a table 4. Insert a new item into a table 5. Delete an item with a given search key 6. Retrieve an item with a given search key 7. Traverse items in sorted search-key order.

What does the pseudocode 'createTable()' do?

It creates an empty table.

What does the pseudocode 'tableIsEmpty()' determine?

It determines whether a table is empty.

What is the purpose of 'tableLength()' in the ADT table?

It determines the number of items in a table.

What does 'tableInsert(newItem)' do?

It inserts newItem into a table with distinct search keys and throws a TableException if the insertion fails.

What does 'tableDelete(searchKey)' return if no item exists?

It returns false if no such item exists.

What does 'tableRetrieve(searchKey)' return if no item matches?

It returns null if no such item exists.

What is the purpose of 'tableTraverse()'?

It traverses a table in sorted search-key order.

What must remain the same for an item stored in the ADT table?

The value of the search key for an item must remain the same.

What does the KeyedItem class contain?

It contains an item's search key and a method for accessing the search-key data field.

What does the TableInterface interface define?

It defines the table operations.

Name a category of linear implementations of the ADT table.

Unsorted, array based.

What is a binary search implementation?

A nonlinear implementation of the ADT table.

What advantages does the binary search tree implementation offer?

It offers several advantages over linear implementations.

What is the ADT priority queue?

An ADT priority queue orders its items by a priority value, removing the item with the highest priority first.

List the operations of the ADT priority queue.

1. Create an empty priority queue 2. Determine whether a priority queue is empty 3. Insert a new item into a priority queue 4. Retrieve and delete the item with the highest priority.

What does 'createPQueue()' do?

It creates an empty priority queue.

What does 'pqIsEmpty()' determine?

It determines whether a priority queue is empty.

What does 'pqInsert(newItem)' do?

It inserts newItem into a priority queue and throws a PQueueException if the queue is full.

What does 'pqDelete()' do?

It retrieves and deletes the item with the highest priority value from the priority queue.

What type of implementation is appropriate for a small number of items in a priority queue?

Sorted linear implementations.

What does an array-based implementation of a priority queue maintain?

It maintains the items sorted in ascending order of priority value.

What does a reference-based implementation of a priority queue maintain?

It maintains the items sorted in descending order of priority value.

What is a heap?

A complete binary tree that is either empty or has a root containing a search key greater than or equal to its children's search keys.

What is a maxheap?

A heap in which the root contains the item with the largest search key.

What is a minheap?

A heap in which the root contains the item with the smallest search key.

What operation does 'createHeap' perform?

It creates an empty heap.

What does 'heapIsEmpty' determine?

It checks whether a heap is empty.

What happens during 'heapInsert(newItem)'?

It inserts newItem into a heap and throws a HeapException if the heap is full.

What does 'heapDelete' do?

It retrieves and deletes a heap's root item, which has the largest search key.

How are priority-queue operations related to heap operations?

The priority value in a priority queue corresponds to a heap item's search key.

What is a disadvantage of heap implementation of a priority queue?

It requires knowledge of the priority queue's maximum size.

What is an advantage of using a heap for a priority queue?

A heap is always balanced and can handle finite, distinct priority values.

What is the strategy of heapsort?

It transforms the array into a heap, removes the heap's root, and transforms the resulting semiheap back into a heap.

How does heapsort compare to mergesort in terms of efficiency?

Both heapsort and mergesort are O(n * log n) in worst and average cases, but heapsort does not require a second array.

What is the purpose of the JCF Map interface?

It provides the basis for numerous other implementations of different kinds of maps.

What method checks if a map is empty?

The method is 'boolean isEmpty()'.

What does the 'put' method in the Map interface do?

It adds a key-value pair to the map.

What is the function of the 'remove' method in the Map interface?

It removes the entry associated with the specified key.

What is a HashMap?

An implementation of the Map interface for an unsorted map.

What is a TreeMap?

An implementation of the SortedMap interface for a sorted map.

What does the Set interface represent?

An ordered collection that stores single value entries and does not allow duplicate elements.

What method adds an element to a Set?

The method is 'boolean add(T o)'.

What does the 'size' method in the Set interface return?

It returns the number of elements in the set.

What is the difference between HashSet and TreeSet?

HashSet is for unsorted sets, while TreeSet is for sorted sets.

What is a priority queue?

A variation of the ADT table that allows retrieval and removal of the item with the largest priority value.

What is the main advantage of heapsort over quicksort?

Heapsort does not require a second array, unlike mergesort.

What is the significance of the ADT table?

It supports value-oriented operations and can be implemented in linear or nonlinear ways.