Se me ocurren dos formas.

Una es que obviamente uses una estructura, donde uno de los campos sea un entero que indique la prioridad. El procedimiento de entrada comprueba que la prioridad no esté repetida (si es necesario), y ordena la lista nuevamente según prioridad.

El otro sería usar un mapa, donde el elemento llave sea la prioridad, de ese modo te cargas de un plumazo la necesidad de ordenar y de comprobar repetidos, solo has de comprobar antes de añadir un campo que la prioridad no está repetida.

Si es a un nivel mas básico, usa un arreglo (o array) de un struct donde uno de los campos sea el entero que indique la prioridad.

También puedes obviar el reorganizar la estructura si el procedimiento de sacar datos simplemente busca el que tenga mas prioridad para extraerlo

Claro que no tenemos claro si estamos hablando de C, C++ y si puedes usar o no contenedores de la STL