CmSc 250 Intro to Algorithms

Priority Queues
  1. Priority queue model
  2. Implementations of priority queues
  3. Binary Heap

Animation

Learning Goals
Exam-like questions

  1. Priority queue model

    2. Usage of queues: in resource management: several users waiting for one and the same resource.
    Priority queues: some users have priority over other users.

    A priority queue is a queue where:

    Requests are inserted in the order of arrival
    The request with highest priority is processed first (deleted from the queue)

    The priority is indicated by a number, the lower the number - the higher the priority.

  2. Implementations of priority queues

    1. Linked list
      • Insert at the beginning - O(1)
      • Find the minimum - O(N)

    2. Binary search tree (BST)
      • Insert O(logN)
      • Find minimum - O(logN)

    3. Binary heap

      4. Better than BST because it does not support links.
      • Insert O(logN)
      • Find minimum O(logN)

      Deleting the minimal element takes a constant time,
      however after that the heap structure has to be adjusted, and this requires O(logN) time.

  3. Binary Heap

    4.

    3. 1. The idea

    A binary heap is a complete binary tree, where each node has a higher priority than its children.
    This is called heap-order property.

    Complete binary tree: Each node has two children, except for the last two levels.
    (The nodes at the last level do not have children.)
    New nodes are inserted at the last level from left to right.

    This is called heap-structure property.

    The tree below is a Complete Binary Heap Tree:

    Next node to be inserted - right child of the yellow node.

    3. 2. Binary heap implementation with an array

    Since the tree is complete, we use the following array implementation:

    Given array A:

    A(1) - contains the root
    The node in A(i) has its left child in A(2*i), its right child in A(2*i+1),
    and its parent in A([i/2]).

    The smallest element is always at the root, thus the access time
    to the element with highest priority is constant O(1).

    6

    10

    12

    15

    17

    21

    23

    20

    19

    34

     

    This is the array that implements the binary heap in the example.
    The nodes of the tree are written in the array level by level from left to right.
    The first element in the array is 6 - this is the node at level 0.
    Then come 10 and 12 - the nodes at level 1.Further we have 15, 17 (children of 10),
    then 18 and 23 (children of 12) - all at level 2.
    Finally we have 20, 19 and 34 - the nodes at the last level.

    Let's take a node in the array and find its parent and its children.

    Consider for example 17.

    Its position in the array is 5.
    Its parent 12 is at position [5/2] = 2
    Its left child is at position 5*2 = 10, this is the element 34,
    and its right child is at position 2*5 + 1 = 11, (still empty).

    3. 3. Basic operations

    3. 3. 1. Insert a node - percolate up

    A hole is created at the bottom of the tree, in the next available position.

    If the new node has a greater value than the parent of the hole - we insert the node in the hole.
    Thus, if the new value to be inserted is 18, our new binary heap would be:

    If the new value is less than its parent, we slide down the parent of the hole, so the hole moves up, and check to see if the new node is less than the parent of the new hole.
    This process is repeated until we find a place for the new node,
    possibly at the very root of the binary heap.

    Let's say we want to insert 16. 16 is less than 17, so we slide down 17, and the hole appears at the node where 17 used to be:

    Since 16 is less than 10, we can insert it in the hole:

    Complexity of insertion: O(logN) in the worst case.
    To insert a node in the worst case we would need to percolate up to the root
    of the binary heap tree. Since the tree is a complete tree,
    the longest path from the bottom to the top is not longer than O(logN),
    where N is the number of nodes in the tree.
    Hence we would do no more than O(logN) percolations up.

    3. 3. 2. Deleting a node - percolate down

    We delete the node at the root - this is the node with highest priority.
    After deleting there is a hole at the root, which has to be filled.

    We may think of sliding the "hole" down and moving up the smaller of the children of the "hole", and repeat this until the hole gets to the bottom. The hole may appear anywhere at the bottom, and if it is not at the last node, the tree is not anymore a complete binary tree.

    (You may try this approach on the tree below and see what happens with the tree.)

    To make sure that the hole appears at the last node, we render the deletion to an insertion in top-down direction. We can try to insert in the hole the last element that has been inserted, i.e. the rightmost element in the lowest row (the last element in the array). Thus in the array the last element will become empty, and the tree will be complete.

    The last element in the example is 18. The hole is at the root.

    Most certainly, 18 will not fit there, and we have to percolate the hole down
    The left child of the hole is with higher priority than the right one.
    We slide the hole down to the left:

    Still, 18 does not fit in the new hole, it has lower priority than its children 15 and 17. The left child of the hole is with higher priority than the right one. We slide the hole down to the left:

    Now 18 fits the hole, and we can safely insert it there:

    Complexity of deletion: O(logN) in the worst case.
    We always delete from the top, hence the time to access the element with highest priority is a constant. However, after deletion we have to fill in the hole at the root. In the worst case we will percolate down to the bottom. Since the hight of the tree is O(logN), where N is the number of nodes, the worst running time is O(logN).

  4. Other heap operations

    5. 4. 1. DecreaseKey(p,d)

    This operation lowers the value of the element at position p by a positive amount d. It is used to increase the priority of an element. We have to find a new position of the element according to its new priority by percolating up.

    4. 2. IncreaseKey(p,d)

    This operation increases the value of the element at position p by a positive amount d. It is used to decrease the priority of an element. We have to find a new position of the element according to its new priority by percolating down.

    4. 3. Remove(p)

    With this operation an element p is removed from the queue. This is done in two steps:

    1. Assigning the highest priority to p - percolate p up to the root.
    2. Deleting the element in the root and filling the hole by percolating down the last element in the queue.

    What does it mean to assign the highest priority?
    We need to have a sentinel value for the priorities - a value that is less than
    all possible values assigned as priorities. For example, if the priorities are positive numbers,
    the value 0 will be a sentinel value.

    4. 4. BuildHeap

    This operation takes as input N elements and places them into an empty heap
    through successive inserts. The worst case running time is bound by O(NlogN).

    However, there is another algorithm to build the binary heap, that runs in O(N) time.

    The idea:

    Given an array of elements to be inserted in the heap, treat the array as a heap with order property violated, and then do operations to fix the order property.

    Let the array A be:
    --- 150  80  40  30  10  70  110   100  20  90  60  50  120  140  130

    A[1] is the root, A[1] = 150. Its children are A[2] and A[3], the children of A[2] are A[4] and A[5], etc. The corresponding tree is:

    In order to fix the order property we compare the nodes with their children starting with the rightmost node at the height 1.

    1. 110 is less that its children - OK
    2. 70 is not less than its children . 50 is the node to go up one level.
    3. 10 is OK
    4. 30 is not less than its children, 20 is the node to go up

    After processing the nodes at height 1 we have the following tree:

    Next we examine the nodes at height 2:

    1. 40 is OK
    2. 80 needs to be percolated down twice.

    The new tree will be:

    Next we examine the node at height 3 - the root

    150 needs to be percolated down three times - until it gets to the bottom

    (Double dotted line indicates two percolates)

    Now the tree is in order.

    Complexity:

    The worst case for a node at height k is k percolations.
    Thus at worst the number of operation is equal to the sum of the heights of the nodes in the tree.

    Theorem: For a perfect binary tree of height h containing N = 2 h+1 - 1 nodes,
    the sum S of the heights of the nodes is S = 2 h+1 - 1 - (h + 1) = O(N)

    Proof:

    We can see that the tree has 1 node at height h, 2 nodes at height h - 1, 4 nodes at height h - 2, etc. Thus we have:

    nodes     height

    1 (20)     h

    2 (21)     h - 1

    4 (22)     h - 2

    8 (23)     h - 3

    …….

    2h           0

     

    Hence we have

    S = S 2i (h - i), i = 0 to h

    S = h + 2(h - 1) + 4(h - 2) + 8 (h - 3) + …. 2(h-2).2 + 2(h-1).1 (1)

    Multiply by 2:

    2S = 2h + 4(h - 1) + 8(h - 2) + 16 (h - 3) + …. 2(h-1).2 + 2(h).1 (2)

    Subtract (1) from (2):

    S = h -2h + 2 + 4 + 8 + …. 2 h
       = - h - 1 + (2 h+1 - 1)
       = (2 h+1 - 1) - (h + 1)

    Note: 1 + 2 + 4 + 8 + …. 2 h = (2 h+1 - 1)

    Hence S = (2 h+1 - 1) - (h + 1)

    Hence the complexity of building a heap with N nodes is linear O(N)

Learning Goals

  • Know what a priority queue is and how it can be implemented.
  • Know what a binary heap is and how it is implemented by an array.
  • Given a queue of elements with assigned priorities,
    be able to build the binary heap on paper and show how the elements are located in an arrray
  • Know the basic operations for a binary heap, be able to perform deletion and insertion on paper.

Exam-like questions

  1. What is a priority queue?
  2. Name at least three ways to implement a priority queue.
  3. What is the "structure property" of a binary heap?
  4. What is the "order property" of a binary heap?
  5. How can a binary heap be implemented by an array?
  6. Given a queue of elements with priorities: 21, 13,17,10,7,11 do the following:
    • Build the binary heap (draw the tree at each step) and show the corresponding array
    • Delete the element with the highest priority, drawing the tree at each step of the deleting procedure
    • Insert a new element with priority 15 and draw the tree at each step of the insertion procedure
  7. What is the complexity of deletion in binary heaps in the worst case? Explain your answer
  8. What is the complexity of insertion in binary heaps in the worst case? Explain your answer.
Back to Contents page
Created by Lydia Sinapova