CODEWITHSUNDEEP
c++calgorithmlistqueue
idjuradj
idjuradj

Reputation: 1465

Algorithm for creating a "relative" priority queue? (c/c++)

I want to make a queue using linked lists. There are numerous algorithms out there for that. But what i'm curious in is how to make a relative priority queue.

Maybe there is a special name for this type of queue, but i don't know it, and i haven't had any luck googling for the solution.

Anyways, let's say i have this struct, which will represent the Node of my list.

struct Node {
    int value;
    Node* next;
}

if i want to create a priority queue (where the element with the least value is first), when i insert for example 5 7 1 8 2, my list should look like this:

1 -> 2 -> 5 -> 7 -> 8

It's not really hard to implement that. What i want to do is - when i insert the first element, other elements should have value relative to the previous element. So, in my example, the list/queue would contain the following values:

1 -> 1 -> 3 -> 2 -> 1

I'm not really sure how i would implement that? Would the following idea be applicable:

in the Node struct i add another field, which would represent the original value. i find the position of the node i'm inserting the same way i would do when creating an ordinary linked list, and then i just say

temp->value = temp->originalValue - previous->originalValue;

Upvotes: 1

Views: 860

Answers (2)

jxh
jxh

Reputation: 70422

You first have to identify where to insert the new node. This involves decrements on the target value, adjusting its relative value in relation to the current in the list. At the point of insertion, you have to point the previous node to the new node, and then adjust the node ahead of the new node with a new relative value.

Node * create_node (int value, Node *next) { /* ... */ }

void insert_relative_priority_queue (Node **head, int value) {
    Node **prev = head, *cur;
    if (*head) {
        cur = *head;
        while (value > cur->value) {
            value -= cur->value;
            prev = &cur->next;
            cur = cur->next;
            if (cur == 0) break;
        }
        *prev = create_node(value, cur);
        if (cur) {
            cur->value -= value;
        }
    } else {
        *head = create_node(value, 0);
    }
}

When you remove from the front of the list, you adjust the value of the new head:

void remove_relative_priority_queue (Node **head) {
    if (*head) {
        Node *cur = *head;
        *head = cur->next;
        if (*head) {
            (*head)->value += cur->value;
        }
        free(cur);
    }
}

Upvotes: 0

andy256
andy256

Reputation: 2881

You need to store extra data in each node, either the relative priority, or a "previous" pointer. Since the next node's relative priority needs to updated whenever a node is removed (how to do that without a prev pointer?), I suggest the "previous" pointer:

struct Node {
    int value;
    Node* next;
    Node* prev;
}

Then a function can evaluate the relative priority:

int relative_priority(Node* node) {
    if (node == NULL)
        return 0;
    if (node->prev == NULL)
        return node->value;
    return node->value - node->prev->value;
}

Note that I'm using C, you'll need to replace NULL with 0 for C++

Upvotes: 1

Related Questions