Implementation of priority queue by AVL Tree data structure

Question

Priority queue: Basic operations: Insertion Delete (Delete minumum 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.
             Delet (Finding minumum and Delete this ) will take o(n) 

BST:
   Insertion/Deltion of minimum = In avg case it will take o(logn) worst case 0(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.

@UmNyobe: In terms of order of grwoth it is same. but in terms of speed it is different.... — Nishant Kumar

Steve Jessop Steve Jessop · Accepted Answer · 2012-05-29T09:39:14

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.

Implementation of priority queue by AVL Tree data structure

3 Answers