the first retrieved. Implementation Naive implementations There are a variety of simple, usually inefficient, ways to implement a priority queue. They provide an analogy to help one understand what a priority queue is. For instance, one can keep all the elements in an unsorted list (O(1) insertion time). Whenever the highest-priority element is requested, search through all elements for the one with the highest priority. (O(n) pull time), insert(node) { list.append(node) } pull() { highest = list.get_first_element() foreach node in list { if highest.priority < node.priority { highest = node } } list.remove(highest) return highest } In another case, one can keep all the elements in a priority sorted list (O(n) insertion sort time), whenever the highest-priority element is requested, the first one in the list can be returned. (O(1) pull time) insert(node) { foreach (index, element) in list { if node.priority < element.priority { list.insert_at_index(node,index) break } } } pull() { highest = list.get_at_index(list.length-1) list.remove(highest) return highest } Usual implementation To improve performance, priority queues are typically based on a heap, giving O(log n) performance for inserts and removals, and O(n) to build the heap initially from a set of n elements. Variants of the basic heap data structure such as pairing heaps or Fibonacci heaps can provide better bounds for some operations. Alternatively, when a self-balancing binary search tree is used, insertion and removal also take O(log n) time, although building trees from existing sequences of elements takes O(n log n) time; this is typical where one might already have access to these data structures, such as with third-party or standard libraries. From a space-complexity standpoint, using self-balancing binary search tree with linked list takes more storage, since it requires to store extra references to other nodes. From a computational-complexity standpoint, priority queues are congruent to sorting algorithms. The section on the equivalence of priority queues and sorting algorithms, below, describes how efficient sorting algorithms can create efficient priority queues. Specialized heaps There are several specialized heap data structures that either supply additional operations or outperform heap-based implementations for specific types of keys, specifically integer keys. Suppose the set of possible keys is {1, 2, ..., C}. When only insert, find-min and extract-min are needed and in case of integer priorities, a bucket queue can be constructed as an array of linked lists plus a pointer , initially . Inserting an item with key appends the item to