1+
2+ struct heap {
3+ int * array ;
4+ int len ;
5+ int max_len ;
6+ bool (* append )(struct heap * self ,int val );
7+ int (* pop )(struct heap * self );
8+ };
9+
10+ bool heap_insert (struct heap * ,int );
11+ int heap_pop (struct heap * );
12+
13+ struct heap * Heap (int max_len ) {
14+ int * array = (int * )malloc (max_len * sizeof (int ));
15+ struct heap * heap = (struct heap * )malloc (sizeof (struct heap ));
16+ heap -> array = array ;
17+ heap -> max_len = max_len ;
18+ heap -> len = 0 ;
19+ heap -> append = heap_insert ;
20+ heap -> pop = heap_pop ;
21+ return heap ;
22+ }
23+
24+ int heap_parent (int index ) {
25+ return (index - 1 ) /2 ;
26+ }
27+
28+ int heap_left (int index ) {
29+ return 2 * index + 1 ;
30+ }
31+
32+ int heap_right (int index ) {
33+ return 2 * index + 2 ;
34+ }
35+
36+ void heap_swap (struct heap * heap ,int parent ,int index ) {
37+ int temp = heap -> array [index ];
38+ heap -> array [index ]= heap -> array [parent ];
39+ heap -> array [parent ]= temp ;
40+ }
41+
42+ void heap_heapify (struct heap * heap ,int index ) {
43+ if (index != 0 ) {
44+ int parent = heap_parent (index );
45+ if (heap -> array [parent ]> heap -> array [index ]) {
46+ heap_swap (heap ,parent ,index );
47+ heap_heapify (heap ,parent );
48+ }
49+ }
50+ }
51+
52+ bool heap_insert (struct heap * heap ,int val ) {
53+
54+ if (heap -> len == heap -> max_len ) {
55+ return false;
56+ }
57+ heap -> array [heap -> len ]= val ;
58+ heap_heapify (heap ,heap -> len );
59+ heap -> len += 1 ;
60+ return true;
61+ }
62+
63+ bool heap_has_left (struct heap * heap ,int index ) {
64+ return heap_left (index )< heap -> len ;
65+ }
66+
67+ bool heap_has_right (struct heap * heap ,int index ) {
68+ return heap_right (index )< heap -> len ;
69+ }
70+
71+ void heap_heapify_reverse (struct heap * heap ,int index ) {
72+
73+ int left = heap_left (index );
74+ int right = heap_right (index );
75+ int minimum = index ;
76+ if (heap_has_left (heap ,index )&& (heap -> array [left ]< heap -> array [minimum ])) {
77+ minimum = left ;
78+ }
79+ if (heap_has_right (heap ,index )&& (heap -> array [right ]< heap -> array [minimum ])) {
80+ minimum = right ;
81+ }
82+ if (minimum != index ) {
83+ heap_swap (heap ,index ,minimum );
84+ heap_heapify_reverse (heap ,minimum );
85+ }
86+ }
87+
88+ int heap_pop (struct heap * heap ) {
89+ if (heap -> len == 0 ) {
90+ return NULL ;
91+ }
92+ int val = heap -> array [0 ];
93+ heap -> len -= 1 ;
94+ heap -> array [0 ]= heap -> array [heap -> len ];
95+ if (heap -> len > 1 ) {
96+ heap_heapify_reverse (heap ,0 );
97+ }
98+ return val ;
99+ }
100+
101+ void heap_free (struct heap * heap ) {
102+ free (heap -> array );
103+ free (heap );
104+ }
105+
106+ typedef struct {
107+ struct heap * heap ;
108+ int k ;
109+ }KthLargest ;
110+
111+
112+ KthLargest * kthLargestCreate (int k ,int * nums ,int numsSize ) {
113+
114+ KthLargest * self = malloc (sizeof (KthLargest ));
115+ self -> heap = Heap (numsSize + 2 );
116+ self -> k = k ;
117+ for (int i = 0 ;i < numsSize ;i ++ ) {
118+ self -> heap -> append (self -> heap ,nums [i ]);
119+ }
120+ while (self -> heap -> len > k ) {
121+ self -> heap -> pop (self -> heap );
122+ }
123+ return self ;
124+ }
125+
126+ int kthLargestAdd (KthLargest * obj ,int val ) {
127+ obj -> heap -> append (obj -> heap ,val );
128+ if (obj -> heap -> len > obj -> k ) {
129+ obj -> heap -> pop (obj -> heap );
130+ }
131+ return obj -> heap -> array [0 ];
132+ }
133+
134+ void kthLargestFree (KthLargest * obj ) {
135+ heap_free (obj -> heap );
136+ free (obj );
137+ }
138+
139+ /**
140+ * Your KthLargest struct will be instantiated and called as such:
141+ * KthLargest* obj = kthLargestCreate(k, nums, numsSize);
142+ * int param_1 = kthLargestAdd(obj, val);
143+
144+ * kthLargestFree(obj);
145+ */