Skip to content
The Chat Archive
palm-2· Google Arena Human Preference 55K

In class we showed how heaps can be implemented using an array. In this problem we…

  1. User

    In class we showed how heaps can be implemented using an array. In this problem we consider using an implementation using pointers. (a) Consider storing a heap as a linked binary tree with pointers. Give pseudo- code on how you would store a heap node, and which modifications you need to make to the heap routines that we discussed in class. What are the runtimes of the heap routines? (b) Now consider storing a heap as a linked list with pointers. Give pseudo-code on how you would store a heap node, and which modifications you need to make to the heap routines that we discussed in class. What are the runtimes of the heap routines? (c) Which of the three heap implementations (array, linked tree, linked list) is preferrable? Justify your answer. (d) Assume you are given two heaps of height h each, that are given as linked binary trees. And assume we do not require that the last level of the heap is “flushed left”, i.e., keys can be in any place in the last level. Give an efficient algorithm that merges those two heaps into one heap (without the “flushed left” condition). Analyze the runtime of your algorithm.

  2. Assistant

    (a) A heap node can be stored as a struct containing the key, the value, and pointers to the left and right child nodes.

    The following modifications need to be made to the heap routines:

    • heapify(): The algorithm for heapifying a node in a linked binary tree is the same as for an array-based heap, except that the node to be heapified is passed as an argument instead of being indexed by its position in the array.
    • insert(): The algorithm for inserting a new node into a linked binary heap is the same as for an array-based heap, except that the new node is inserted at the end of the heap and then heapified.
    • delete(): The algorithm for deleting a node from a linked binary heap is the same as for an array-based heap, except that the node to be deleted is first found by traversing the heap from the root to the leaf that contains the node.

    The runtimes of the heap routines are the same as for an array-based heap.

    (b) A heap node can be stored as a struct containing the key, the value, and pointers to the next and previous node in the linked list.

    The following modifications need to be made to the heap routines:

    • heapify(): The algorithm for heapifying a node in a linked list is the same as for an array-based heap, except that the node to be heapified is passed as an argument instead of being indexed by its position in the array.
    • insert(): The algorithm for inserting a new node into a linked list heap is the same as for an array-based heap, except that the new node is inserted at the end of the list and then heapified.
    • delete(): The algorithm for deleting a node from a linked list heap is the same as for an array-based heap, except that the node to be deleted is first found by traversing the list from the head to the node.

    The runtimes of the heap routines are the same as for an array-based heap.

    (c) The array-based heap implementation is preferable because it is more efficient than the linked tree and linked list implementations. The array-based heap implementation has a runtime of O(log n) for all heap operations, while the linked tree and linked list implementations have a runtime of O(n) for

Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.