1 files changed, 49 insertions, 0 deletions
diff --git a/rushs/evalexpr/heap/pop.c b/rushs/evalexpr/heap/pop.c
new file mode 100644
index 0000000..55e063f
--- /dev/null
+++ b/rushs/evalexpr/heap/pop.c
@@ -0,0 +1,49 @@
+#include <assert.h>
+#include <stdlib.h>
+
+#include "heap.h"
+
+void heapify2(struct heap *h, size_t i)
+{
+    size_t max = i;
+    if (2 * i + 1 < h->size && h->array[2 * i + 1] > h->array[max])
+        max = 2 * i + 1;
+    if (2 * i + 2 < h->size && h->array[2 * i + 2] > h->array[max])
+        max = 2 * i + 2;
+    if (max != i)
+    {
+        int tmp = h->array[i];
+        h->array[i] = h->array[max];
+        h->array[max] = tmp;
+        heapify2(h, max);
+    }
+}
+
+int pop(struct heap *heap)
+{
+    assert(heap->size != 0);
+    if (heap->size == 1)
+    {
+        heap->size--;
+        return heap->array[0];
+    }
+    else
+    {
+        int res = heap->array[0];
+        heap->array[0] = heap->array[heap->size - 1];
+        heap->size--;
+        heapify2(heap, 0);
+        if (heap->size < heap->capacity / 2 && heap->capacity > 8)
+        {
+            heap->array =
+                realloc(heap->array, (heap->capacity / 2) * sizeof(int));
+            if (heap->array == NULL)
+            {
+                free(heap);
+                return -1;
+            }
+            heap->capacity /= 2;
+        }
+        return res;
+    }
+}