/Saving-Heap-Position-Using-Hash-Table

Primary LanguageC

Saving Heap Position Using Hash Table

Sample that implements a heap and saves the location of the elements in a hash table.

As many of you may not be familiar with C, you may find it difficult to understand. Hence, I would recommend you don't go through the entire code. Instead just try to understand the main idea the program does by following the video.

Video recording of SI session that discusses the programming assignment # and the sample code in more detail

How to run the code (Mac/Linux)

chmod +x ./compile.sh
./compile.sh
./main

Sample Input

Input is already implemented in main.c itself. It inputs the following (airports, dvalue) in the heap and has table:

  1. (GHI, 4)
  2. (JKL, 7)
  3. (MNO, 3)
  4. (PQR, 1)
  5. (STU, 10)
  6. (VQX, 8)
  7. (YYZ, 4)
  8. (NUY, 100)

It then prints all the heap and hash elements.

Then decrease_key is called for the following airports:

  1. (STU, 10) -> (STU, 2)
  2. (NUY, 100) -> (NUY, 1)

Finally, it prints all the heap and hash elements again.

Sample Output

Printing heap elements...
<-----START----->
0: Airport PQR has shortest distance 1
1: Airport MNO has shortest distance 3
2: Airport GHI has shortest distance 4
3: Airport JKL has shortest distance 7
4: Airport STU has shortest distance 10
5: Airport VQX has shortest distance 8
6: Airport YYZ has shortest distance 4
7: Airport NUY has shortest distance 100
<-----END------->
Printing hash elements...
<-----START----->
53: NUY is at heap index 7
439: YYZ is at heap index 6
452: GHI is at heap index 2
475: MNO is at heap index 1
560: JKL is at heap index 3
583: PQR is at heap index 0
691: STU is at heap index 4
997: VQX is at heap index 5
<-----END------->

Decreasing the dvalues of airports STU and NUY. Print the updated results.

Printing heap elements...
<-----START----->
0: Airport PQR has shortest distance 1
1: Airport NUY has shortest distance 1
2: Airport GHI has shortest distance 4
3: Airport STU has shortest distance 2
4: Airport MNO has shortest distance 3
5: Airport VQX has shortest distance 8
6: Airport YYZ has shortest distance 4
7: Airport JKL has shortest distance 7
<-----END------->
Printing hash elements...
<-----START----->
53: NUY is at heap index 1
439: YYZ is at heap index 6
452: GHI is at heap index 2
475: MNO is at heap index 4
560: JKL is at heap index 7
583: PQR is at heap index 0
691: STU is at heap index 3
997: VQX is at heap index 5
<-----END------->