I need an advice for optimal implementation of a program with priority queue and search

I have to make a program to read the list of patient of an hospital from a file, every patient have a priority.

So i decide to make the priority queue in a binary heap because insert and deletion are O log(n), and obtain the patient to be treated is O(1), good enough for this program. I stored the heap in a dynamic array of pointers to the struct patient. This works fine.

But also i have to be able to find a patient by his security number, and this is not possible in a heap (so far i know).

So i was thinking to make a hash table where when i add a patient to the heap hi is going to be added to the hash table too (all this work is with pointers).

This is a good way to proceed? or i have to rethink the data structures to be use and remake the program using another ADT? (please no).

Code of the structs:

typedef struct patient {
  char name[20];
  char lastName[20];
  char securityNumber[20];
  char birthDate[8];
  int priority;
}PATIENT;

typedef struct binary_heap{
  PAT** patHeap;
  int n;
}HEAP;

Insert and deletion are good enough in a heap and a hash table. But have more pointers is more memory to be use.

This is my really first time making this kind of "real programs" so i will be very thankful if you people can give any advice.

Thanks!

Solution

question: how to select patient via social security number?

IF the social security number is a field in the struct being used to make nodes in the linked list. The simply start at the head pointer of the linked list, stepping one by one through the linked list. at each node in the linked list, compare the target social security number with the entry in the node. When a match is found, then the pointer to that node is pointing to the desired patient.

However, learn a bit about social security numbers. For instance, they are not ###-##-#### but rather ###-##-####c, where the final 'c' (a character) is rarely used these days.

if you had posted the code, 
then we could post matching code 
for the function that finds a patient 
via their social security number.

BTW:
a patients social security number is a bit of sensitive information. 
so the code should encrypt that field.