Heap using double linked list

Question

Suppose one wants to implement a Max Heap using a doubly linked list. Can one achieve the same complexity for the operations Insert, ExtractMaxHeap and MaxHeapify using a doubly linked list as compared to the standard array implementation.

My answer is we can do all three operation in log(n) time using array implementation. However, for doubly linked list

Insert - logn
ExtractMaxHeap -o(1)
MaxHeapify - o(logn)

Answer 1

In a standard array implementation one can find the child of an element in constant time. If the current node is identified by index i, then the left child is identified by index 2i+1, and the right child by index 2i+2^*.

*_{In heaps with k children, that would be ki+1, ki+2, ..., ki+k. The principle is the same}

Given a node in a doubly linked list, there is no way to get to the first child in constant time. The deeper the node is in the list, the more steps it will take -- walking the chain of the linked list -- to get to the sub-chain having the child nodes.

In the array implementation you don't need to visit the elements that lie between a node and its children. The access to the child (by index) is immediate. This is not true in a linked list. You have no other choice than to first visit the next node, then its next, ...etc. until you arrive at the "index" where the child node is at. The length of this chain, to walk towards the child, increases exponentially with the depth of the node where you start from.

A similar inefficiency occurs when you need to find the parent of a node.

As all basic operations on a heap involve swapping child with parent values, this problem gives these operations a worse time complexity in a doubly linked list implementation than in the array implementation.

Answer 2

If the elements are stored entirely in a linked list, with no other structure, then no. If the elements are sorted, then insertion will be O(n). If they are not, then extraction will be O(n).