algorithmdata-structures

Implementation of priority queue by AVL Tree data structure


Priority queue: Basic operations: Insertion Delete (Delete minimum element)

Goal: To provide efficient running time or order of growth for above functionality.

Implementation of Priority queue By:

Linked List: Insertion will take O(n) in case of insertion at end O(1) in case of 
             insertion at head.
             Delete (Finding minimum and deleting it) will take O(n) 

BST:
   Insertion/Deletion of minimum = In avg case it will take O(logn) worst case O(n)

AVL Tree: 
   Insertion/deletion/searching: O(log n) in all cases.

My confusion goes here:

Why not we have used AVL Tree for implementation of Priority queue, Why we gone for Binary heap...While as we know that in AVL Tree we can do insertion/deletion/searching in O(log n) in worst case.


Solution

  • Complexity isn't everything, there are other considerations for actual performance.

    For most purposes, most people don't even use an AVL tree as a balanced tree (Red-Black trees are more common as far as I've seen), let alone as a priority queue.

    This is not to say that AVL trees are useless, I quite like them. But they do have a relatively expensive insert. What AVL trees are good for (beating even Red-Black trees) is doing lots and lots of lookups without modification. This is not what you need for a priority queue.

    As a separate consideration -- never mind your O(log n) insert for a binary heap, a fibonacci heap has O(1) insert and O(log N) delete-minimum. There are a lot of data structures to choose from with slightly different trade-offs, so you wouldn't expect to see everyone just pick the first thing that satisfies your (quite brief) criteria.