Heap Sort
/*
Time limit: 1000ms
Memory limit: 256mb
---------------------Copy the following code, complete it and submit---------------------
I, <Your Full Name>, am submitting the assignment for
an individual project.
I declare that the assignment here submitted is original except for
source material explicitly acknowledged, the piece of work, or a part
of the piece of work has not been submitted for more than one purpose
(i.e. to satisfy the requirements in two different courses) without
declaration. I also acknowledge that I am aware of University policy
and regulations on honesty in academic work, and of the disciplinary
guidelines and procedures applicable to breaches of such policy and
regulations, as contained in the University website
http://www.cuhk.edu.hk/policy/academichonesty/.
It is also understood that assignments without a properly signed
declaration by the student concerned will not be graded by the
teacher(s).
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define INF -1
typedef enum {INSERT = 1, DELETE, TOP, ERROR_OP} OP;
struct Student_Record{
long long int ID;
int grade;
};
struct Heap {
int capacity;
int size;
struct Student_Record* arr;
};
typedef struct Heap* HeapADT;
// Create a max heap with a given capacity
HeapADT CreateHeap(int capacity) {
HeapADT heap = (HeapADT) malloc(sizeof(struct Heap));
heap->capacity = capacity;
heap->size = 0;
heap->arr = (struct Student_Record*) malloc((capacity + 1) * sizeof(struct Student_Record));
return heap;
}
// Adjust the heap as a min heap
void HeadAdjust(HeapADT heap, int nodeid, int heapsize) {
// WRITE YOUR CODE HERE
}
// Sort the heap and output the result
void HeapSort(HeapADT heap) {
// WRITE YOUR CODE HERE
}
int main()
{
int n;
scanf("%d", &n);
HeapADT heap = CreateHeap(n);
for (int i = 1; i <= n; ++i)
{
struct Student_Record item;
scanf("%lld %d", &item.ID, &item.grade);
heap->arr[i] = item;
heap->size++;
}
HeapSort(heap);
return 0;
}
---------------------------------------End of Code---------------------------------------
## [Heap Sort]
You are given an array of $n$ student grade records, each represented as a tuple $(student_id, grade)$. Your task is to sort these records in **descending order** based on their grades using the **heap sort algorithm**.
**student_id** is guaranteed to be a unique 9-digit integer starting with a non-zero number.
If two students have identical grades, their order is determined by their IDs: the student with the smaller ID appears first.
The heap sort algorithm must be implemented explicitly (predefined sorting functions are not allowed).
### Input
The first line contain an integer number $n(1\leq n \leq 10^5)$, representing the number of student records.
The next $n$ lines each contain two integers, student_id and grade, separated by a space.
Notice that a grade is an integer between 0 and 100, and each student_id is a 9-digit number.
### Output
Print $n$ lines, each containing a tuple $(student_id, grade)$, sorted according to the following rules:
1. Descending order of grades (highest to lowest).
2. Ascending order of student IDs for students with the same grade (smaller ID first).
### Example
**Input**
```
5
123456789 10
234567890 20
345678901 30
456789012 90
567890123 10
```
**Output**
```
456789012 90
345678901 30
234567890 20
123456789 10
567890123 10
```
**Explanation**
Submit