04: restricted containers #1

Stacks | Queues | Dequeue | Binary Heaps | Priority Queues

Stack

A stack is a Last-In-First-Out (LIFO) collection
  1. Start:
    Stack
  2. push(1)
    Stack
  3. push(2)
    Stack
  4. pop: returns 2
    Stack
  5. push(3)
    Stack
  6. push(4)
    Stack
  7. push(5)
    Stack

C++ Stack Usage

1:  
// cppStackExample.cpp - download here

2:  

3:  
#include
 
<
stack>

4:  
#include
 
<
iostream>

5:  

6:  
int
 
main(
int
 
argc, 
char
 
argv[
]
)
{

7:  

8:  
 
 
std:
:
stack<
int
>
 
int_stack;

9:  
 
 
int_stack.push(
1)
;

10: 
 
 
int_stack.push(
2)
;

11: 

12: 
 
 
//in the std library top and pop are two seperate methods

13: 
 
 
std:
:
cout 
<
<
 
int_stack.top(
)
 
<
<
 
std:
:
endl;

14: 
 
 
int_stack.pop(
)
;

15: 

16: 
 
 
int_stack.push(
3)
;

17: 
 
 
int_stack.push(
4)
;

18: 
 
 
int_stack.push(
5)
;

19: 

20: 
 
 
return
 
0;

21: 
}


Simple Queue

Array Based Circular Buffers are sometimes useful in limited resource environments such as a network card integrated circuit.

Push

  1. Start:
    ArrayCircularBufferInsertStart
  2. Push
    ArrayCircularBufferInsertStart
  3. Push
    ArrayCircularBufferInsertStart
  4. Push
    ArrayCircularBufferInsertStart
  5. Pop
    ArrayCircularBufferInsertStart
  6. Pop
    ArrayCircularBufferInsertStart

  7. After more pushes and pops
    ArrayCircularBufferInsertStart
  8. Push
    ArrayCircularBufferInsertStart
  9. Push
    ArrayCircularBufferInsertStart

c++ deque

  • A deque is a double-ended queue
  • Insertion at the front and back is fast
  • Random access is fast
  1. Start:
    DequeFinal
  2. push_front(0);
    DequeFinal
  3. push_front(1);
    push_front(2);
    push_front(3);
    DequeFinal
  4. push_front(4);
    DequeFinal
  5. push_back(0);
    DequeFinal
  6. push_back(1);
    push_back(2);
    push_back(3);
    DequeFinal
  7. push_back(4);
    DequeFinal
  8. push_front(5);
    push_front(6);
    push_front(7);
    push_front(8);
    DequeFinal
  • C++ deque usage
    1:  
    // cppDequeExample.cpp - download here

    2:  

    3:  
    #include
     
    <
    deque>

    4:  
    #include
     
    <
    iostream>

    5:  

    6:  
    int
     
    main(
    int
     
    argc, 
    char
     
    argv[
    ]
    )
    {

    7:  
     
     

    8:  
     
     
    std:
    :
    deque<
    int
    >
     
    dq1;

    9:  
     
     
    dq1.push_front(
    1)
    ;

    10: 
     
     
    dq1.push_front(
    2)
    ;

    11: 
     
     
    dq1.push_back(
    3)
    ;

    12: 

    13: 
     
     
    for
    (
    size_t
     
    =
     
    0;
     
    <
     
    dq1.size(
    )
    ;
     
    ++i)
    {

    14: 
     
     
     
     
    std:
    :
    cout 
    <
    <
     
    dq1[
    i]
     
    <
    <
     
    " "
    ;

    15: 
     
     
    }

    16: 

    17: 
     
     
    return
     
    0;

    18: 
    }

  • Deque Algorithms
    1:  

    2:  
    void
     
    Deque:
    :
    push_back(
    int
     
    value)
    {

    3:  
     
     
    if
    (
    m_LastBlockStop 
    == 
    m_BlockSize)
    {

    4:  
     
     
     
     
    m_MiddleBlocks.push_back(
    m_LastBlock)
    ;

    5:  
     
     
     
     
    m_LastBlockStop 
    0;

    6:  
     
     
     
     
    m_LastBlock 
    new
     
    int
    [
    m_BlockSize]
    ;

    7:  
     
     
    }

    8:  
     
     
    m_LastBlock[
    m_LastBlockStop]
     
    value;

    9:  
     
     
    ++m_LastBlockStop;

    10: 
     
     
    ++m_Size;

    11: 
    }

    12: 

    13: 
    void
     
    Deque:
    :
    push_front(
    int
     
    value)
    {

    14: 
     
     
    if
    (
    m_FirstBlockStart 
    == 
    m_BlockSize)
    {

    15: 
     
     
     
     
    m_MiddleBlocks.push_front(
    m_FirstBlock)
    ;

    16: 
     
     
     
     
    m_FirstBlockStart 
    0;

    17: 
     
     
     
     
    m_FirstBlock 
    new
     
    int
    [
    m_BlockSize]
    ;

    18: 
     
     
    }

    19: 
     
     
    m_FirstBlock[
    m_BlockSize 
    m_FirstBlockStart 
    1]
     
    value;

    20: 
     
     
    ++m_FirstBlockStart;

    21: 
     
     
    ++m_Size;

    22: 
    }

    23: 

    24: 
    int
     
    Deque:
    :
    getBlock(
    int
     
    block_index)
    {

    25: 
     
     
    std:
    :
    list<int 
    *>
    :
    :
    iterator 
    iter 
    m_MiddleBlocks.begin(
    )
    ;

    26: 
     
     
    for
    (
    int
     
    0;
     
    <
     
    block_index;
     
    ++i)
    {

    27: 
     
     
     
     
    ++iter;

    28: 
     
     
    }

    29: 
     
     
    return
     
    *iter;

    30: 
    }

    31: 

    32: 
    int
     
    Deque:
    :
    get(
    int
     
    index)
    {

    33: 
     
     
    if
    (
    index 
    <
     
    m_FirstBlockStart)
    {

    34: 
     
     
     
     
    int
     
    block_index 
    m_BlockSize 
    m_FirstBlockStart 
    index;

    35: 
     
     
     
     
    return
     
    m_FirstBlock[
    block_index]
    ;

    36: 
     
     
    }
     
    else
     
    if
    (
    index 
    <
     
    m_Size 
    m_LastBlockStop)
    {

    37: 
     
     
     
     
    index 
    -= 
    m_FirstBlockStart;

    38: 
     
     
     
     
    int
     
    block 
    index 
    m_BlockSize;

    39: 
     
     
     
     
    int
     
    curr 
    getBlock(
    block)
    ;

    40: 
     
     
     
     
    int
     
    item 
    index 
    m_BlockSize;

    41: 
     
     
     
     
    return
     
    curr[
    item]
    ;

    42: 
     
     
    }
     
    else
     
    {

    43: 
     
     
     
     
    int
     
    last_index 
    index 
    m_FirstBlockStart 
    (
    m_MiddleBlocks.size(
    )
     
    m_BlockSize)
    ;

    44: 
     
     
     
     
    return
     
    m_LastBlock[
    last_index]
    ;

    45: 
     
     
    }

    46: 
    }

    47: 

Simple Priority Queue

A priority queue allows the user to dequeue the largest or smallest element each time.
  • A simple priority queue is a linked list
  • On insertion the item is put in ascending or descending order (O(n))
  • For removal, the head of the list is chosen and removed (O(1))

Binary Heaps

A max-heap or min-heap can be used to create a priority queue that has O(lg(n)) insertion time and O(lg(n)) removal time
  • A max-heap is a tree based data structure where each node is larger or equal to all of its children
  • A min-heap is a tree based data structure where each node is smaller or equal to all of its children
MaxHeap
  • Parent(i): lower_bound((i + 1) / 2) - 1
  • LeftChild(i): (2 * i) + 1
  • RightChild(i): (2 * i) + 2

Algorithms on Heaps

Bottom-up Heapify

  • "To restore the heap condition when a node's priority is increased, we move up the heap" -Robert Sedgewich

  • Bottom-up Heapify can also be used as the basis for inserting an element into a heap-based priority queue
1: 
algorithm
 
fixUp(
array 
a, 
int
 
k)
{

2: 
 
 
while
(
>
 
&& 
a[
parent(
k)
]
 
<
 
a[
k]
)
{

3: 
 
 
 
 
exch(
a[
k]
a[
parent(
k)
]
)
;

4: 
 
 
 
 
parent(
k)
;

5: 
 
 
}

6: 
}

Heap Insertion

  1. Start:
    HeapInsert
  2. Insert 30 at bottom of array
    HeapInsert
  3. Exchange 30 and 4
    HeapInsert
  4. Exchange 30 and 5
    HeapInsert
  5. Exchange 30 and 20
    HeapInsert

Top-down Heapify

"To restore the heap condition when a node's priority is decreased, we move down the heap" -Robert Sedgewich
1:  
algorithm
 
fixDown(
array 
d, 
int
 
k, 
int
 
size)
{

2:  
 
 
while
(
leftChild(
k)
 
<= 
size)
{

3:  
 
 
 
 
leftChild(
k)
;

4:  
 
 
 
 
if
(
there 
is 
right 
child 
and 
the 
right 
child 
is 
larger)
{

5:  
 
 
 
 
 
 
rightChild(
k)

6:  
 
 
 
 
}

7:  
 
 
 
 
if
(
d[
k]
 
is 
less 
than 
d[
j]
)
{

8:  
 
 
 
 
 
 
exchange(
d[
k]
d[
j]
)

9:  
 
 
 
 
}
 
else
 
{

10: 
 
 
 
 
 
 
break
;

11: 
 
 
 
 
}

12: 
 
 
 
 
j;

13: 
 
 
}

14: 
}

Remove Maximum

  1. Start:
    HeapInsert
  2. Exchange the highest element with the last in the array, but remove the highest element
    HeapInsert
  3. Exchange 4 and 20
    HeapInsert
  4. Exchange 4 and 5
    HeapInsert
  5. Done because 4 is greater than 3

Increase Key

  • Increase Key and then call fixup

Decrease Key

  • Decrease Key and then call fixdown

Delete Key

  • Increase Key to become the largest in the heap
  • Call fixup
  • Exchange the root element with the last element
  • Call fixdown

Duplicate Keys

  • Duplicate keys should have one key with two values associated or a count
  • When inserting, how do you know if it is a duplicate?
  • The array is not sorted, so you must use an O(n) search
  • Or you can keep a perfect hashtable of keys to element pointers. This takes O(1) time once the table is constructed
  • In lecture 16 we will talk about hashtable algorithms

Heap Based Priority Queue

  • A max-heap is used when desiring the highest priority element
  • Insertion is done using insert and bottom-up heapify O(lg(n))
  • Removal of the highest node is done by recording the highest and then exchanging with the last element, then doing top-down heapify O(lg(n))

C++ Priority Queue

1:  
// cppPriorityQueueExample.cpp - download here

2:  

3:  
#include
 
<
queue>

4:  
#include
 
<
iostream>

5:  
#include
 
<
functional>

6:  

7:  
int
 
main(
int
 
argc, 
char
 
*argv[
]
)
{

8:  
 

9:  
 
 
std:
:
priority_queue<
int
>
 
max_queue;

10: 
 
 
std:
:
priority_queue<
int, 
std:
:
vector<
int
>
std:
:
greater<
int
>
 
>
 
min_queue;

11: 
 
 
//std::priority_queue uses std::vector and std::less by default

12: 

13: 
 
 
min_queue.push(
3)
;

14: 
 
 
min_queue.push(
2)
;

15: 
 
 
min_queue.push(
1)
;

16: 

17: 
 
 
max_queue.push(
3)
;

18: 
 
 
max_queue.push(
2)
;

19: 
 
 
max_queue.push(
1)
;

20: 

21: 
 
 
std:
:
cout 
<
<
 
"top of max_queue: "
 
<
<
 
max_queue.top(
)
 
<
<
 
std:
:
endl;

22: 
 
 
//prints: top of max_queue: 3

23: 
 
 
max_queue.pop(
)
;

24: 

25: 
 
 
std:
:
cout 
<
<
 
"top of min_queue: "
 
<
<
 
min_queue.top(
)
 
<
<
 
std:
:
endl;

26: 
 
 
//prints: top of min_queue: 1

27: 
 
 
min_queue.pop(
)
;

28: 
 
 
return
 
0;

29: 
}

References

  1. Adam Drozdek. "Data Structures and Algorithms in C++"
  2. Algorithms in C++, Parts 1-4: Robert Sedgewick. pages 383-387, 406-414