Bucket queue Data structure

Source: Wikipedia.com

A bucket queue is a priority queue data structure optimized for scenarios where elements have a small range of priorities. This data structure can significantly improve the performance of algorithms like Dijkstra and A*, especially when edge weights are small integers. [for example, if the distances are small or if the weights represents the time in shortest path problem].

Idea:

It organizes elements into buckets based on their priority. Each bucket corresponds to a priority level, allowing efficient insertion and extraction.

Example: Converting array into bucket queue

Consider an array of integers where each integer represents a priority:

 array = [3, 1, 4, 2, 5, 1, 2, 4]

1- Initialize empty buckets: We create a list of empty buckets where each bucket corresponds to a specific priority. The number of buckets is determined by the range of priorities (from 1 to the maximum value in the array, which is 5 in this case).

buckets = [[], [], [], [], []]

Each index in buckets represents a priority level. For example, buckets[0] is for priority 1, buckets[1] is for priority 2, and so on.

2- Insert elements into buckets: we go through each element in the array and place it into the corresponding bucket based on its priority.

• insert 3(priority 3): buckets = [[], [], [3], [], []]
• insert 1(priority 1): buckets = [[1], [], [3], [], []]
• insert 4(priority 4): buckets = [[1], [], [3], [4], []]
• insert 2(priority 2): buckets = [[1], [2], [3], [4], []]
• insert 5(priority 5): buckets = [[1], [2], [3], [4], [5]]
• insert 1(priority 1): buckets = [[1, 1], [2], [3], [4], [5]]
• insert 2(priority 2): buckets = [[1, 1], [2, 2], [3], [4], [5]]
• insert 4(priority 4): buckets = [[1, 1], [2, 2], [3], [4, 4], [5]]

Now, each index in buckets represents a priority level: buckets[0] corresponds to priority 1, buckets[1] corresponds to priority 2, and so on..

Implementation in CPP

1- Initialization:

Target: Setting up the structure to hold buckets.

Steps: Initialize a vector of lists where each index represents a priority level, and each list represents a bucket.

Time complexity: O(1)

std::vector<std::list<int>> buckets;

2- Insertion:

Target: Adding element to the appropriate bucket.

Steps:

1. Check the availability of the priority.
2. Append the element to the bucket.

Time complexity: O(1); both direct access to the bucket takes and push_back function take constant time.

void insert(int priority, int value){
  if(priority >= 0 && priority <= buckets.size()) 
    buckets[priority].push_back(value);
}

3- Extract_min:

Target: Removing and returning the element with the smallest priority.

Steps:

1. Iterate over the buckets starting from the lowest priority.
2. find the first non-empty bucket.
3. remove and return the front element from that bucket, return -1 if the bucket is empty.

Time complexity: O(m); where m is the number of buckets.

int extract_min() {
  // Iterate over the buckets starting from the lowest priority
  for(int i = 0; i < buckets.size(); i++){
    // find the first non-empty bucket
    if(!buckets[i].empty()) {
      int min_val = buckets[i].front();
      // remove and return the front element from that bucket
      buckets[i].pop_front();
      return min_val;
    }
  }
  return -1;  // the bucket is empty
}

4- Check if empty:

Target: Return true if the bucket queue is empty.

Steps:

1. Iterate over all buckets inside the list.
2. If any bucket is non-empty, return false.
3. Return true if all the buckets are empty.

Time complexity: O(m); where m is the number of buckets.

bool is_empty() {
  // Iterate over all buckets inside the list.
  for(auto& bucket : buckets)
    // If any bucket is non-empty, return false.
    if(!bucket.empty()) 
      return false;
    return true;  // return true if all the buckets are empty
}

5- Deletion:

Target: Remove a specific element from the bucket queue.

Steps:

1. Find the priority of the element to be deleted[where the element is located]
2. Remove the element from the bucket.

Time complexity: O(n); where n is the number of elements of the corresponding bucket.

Note that if the bucket is empty after removal, it still EXIST but empty.

void delete_element(int priority, int value) {
  if(priority >= 0 && priority <= buckets.size()) {
    // find the priority of the element to be deleted
    auto& bucket = buckets[priority];
    // remove the element from the bucket
    bucket.remove(value); 
  }
}

6- Searching:

Target: Check if a specific element is present in the bucket queue.

Steps:

1. Find the priority of the element to search for[where the element is located].
2. Search the bucket for the element.
3. Return true of the element is found, false otherwise.

Time complexity: O(n); where n is the number of elements of the corresponding bucket.

bool search_element(int priority, int value){
  if(priority >= 0 && priority <= buckets.size()) {
    // Find the priority of the element to search for
    auto& bucket = buckets[priority];
    // Search the bucket for the element, and
    // Return true of the element is found, false otherwise.
    return std::find(bucket.begin(), bucket.end(), value) != bucket.end();
  }
  return false;
}

7- Traversing:

Target: Traverse over all elements for each bucket inside the bucket queue.

Steps:

1. Iterate over each bucket starting from the lowest priority
2. For each bucket, iterate over its elements list.
3. Process/ print each element.

Time complexity: O(m * n); where m is the number of buckets, and n is the number of elements in each bucket.

void traverse() {
  // Iterate over each bucket starting from the lowest priority
  for(int priority = 0; priority < buckets.size(); priority++) {
    auto& bucket = buckets[priority];
    // For each bucket, iterate over its elements list.
    for(auto& value : bucket) {
      // print each element.
      std::cout << "Priority " << priority+1 << ": " << value << std::endl;
    }
  }
}

Bucket queue effect on Dijkstra algorithm

Dijkstra algorithm finds the shortest path from a start node to all other vertices in a graph with non-negative weights.

Traditional implementation:

Traditionally, priority queue based on binary heap is used. The operations on the heap(insert, extract_min) take O(log n) time.

Bucket queue implementation:

Operations can be more efficient O(1) if the graph has small integer weights.

But why?

Because if the graph has bigger weights, this means that the vector of buckets will be very big, which will affect the memory consumption, which results in higher time consumption for handling the operations such like insertion and extract_min. This is the reason behind the bucket queue efficiency especially for small weights.

Steps:

1. Initialization:

• Initialize distances to all vertices as infinity, except the start vertex, it will be set to 0.
• Insert the source vertex inside the bucket queue with priority 0.

std::vector<int> dist<V, INT_MAX>
BucketQueue bq<V>;
bq.insert(0, src);
dist[src] = 0;

2. Relaxation:

• While the bucket queue is not empty, extract the minimum element.
• For each adjacent vertex, if a shorter path is found, update the distance and re-insert the vertex with the new distance.

while(!bq.is_empty()){
  int min_element = bq.extract_min();
  for(auto& [V: weight] : adj[min_element) {
    if(dist[V] + weight < dist[V]) {
      dist[V] = dist[u] + weight;
      bq.insert(dist[v], V)
    }
  }
}

Tracing steps in detail:

Consider a graph with 5 vertices (0, 1, 2, 3, 4) and the following edges with weights.

0 -> 1, 2

0 -> 2, 4

1 -> 2, 1

1 -> 3, 7

2 -> 4, 3

3 -> 4, 1

1. Dist = [0, ∞, ∞, ∞, ∞]; bq = [[0], [], [], [], [], [], …..]

Process vertex 0:

2. extract_min from bq:

• Remove vertex 0 from the first bucket(distance 0).
• bq becomes [[], [], [], [], [], [], [], ....]

3. Update distances for neighbors of vertex 0:

• For edge(0 -> 1, weight 2): new_distance: dist[1] = min(∞, 0 + 2) = 2
• For edge (0 -> 2, weight 4): new_distance: dist[2] = min(∞, 0 + 4) = 4

4. Insert updated vertices into bq :

• Insert vertex 1 into bucket index 2 (distance 2 as the distance is the priority here): bq[2].push_back(1)
• Insert vertex 2 into bucket index 4 (distance 4): bq[4].push_back(2)
• Here, bq becomes [[], [], [1], [], [2], [], [], ...]

Process vertex 1:

5. extract_min from bq:

• Remove vertex 2 from the first bucket.
• bq becomes [[], [], [], [], [2], [], [], ....]

6. Update distances for neighbors of vertex 1:

• For edge(1 -> 2, weight 1): new_distance: dist[2] = min(4, 2 + 1) = 3 (Updated).
• For edge (1 -> 3, weight 7): new_distance: dist[3] = min(∞, 2 + 7) = 9

7. Insert updated vertices into bq :

• Insert vertex 2 into bucket index 3(distance 3): bq[3].push_back(2)
• Insert vertex 3 into bucket index 9(distance 9): bq[9].push_back(3)
• Here, bq becomes [[], [], [], [2], [], [], [], [], [], [3]...]

Process vertex 2:

8. extract_min from bq:

• Remove vertex 3 from the first bucket.
• bq becomes [[], [], [], [], [], [], [], [], [], [3]...]

9. Update distances for neighbors of vertex 2:

• For edge(2 -> 4, weight 3): new_distance: dist[4] = min(∞, 3 + 3) = 6

10. Insert updated vertices into bq :

• Insert vertex 4 into bucket index 6(distance 6): bq[6].push_back(4)
• Here, bq becomes [[], [], [], [], [], [], [4], [], [], [3]...]

Process vertex 3:

11. extract_min from bq:

• Remove vertex 3 from the first bucket.
• bq becomes [[], [], [], [], [], [], [4], [], [], []...]

12. Update distances for neighbors of vertex 3:

• For edge(3 -> 4, weight 1): new_distance: dist[4] = min(6, 9+ 1) = 6 (no change since 6 is already the shortest distance).

13. No new insertion into bq is needed as the distance to vertex 4 is not updated.

Process vertex 4:

14. extract_min from bq:

• Remove vertex 4from the first bucket.
• bq becomes [[], [], [], [], [], [], [], [], [], []...]

15. No updates needed, as there are no outgoing edges from vertex 4.

Final distances: dist= [0, 2, 3, 9, 6]

Note: Bucket queue also used in the implementation of A* algorithm in the same logic.

Code:

• Bucket queue data structure implementation
• Dijkstra algorithm implementation using bucket queue
• A* algorithm implementation using bucket queue