-
Notifications
You must be signed in to change notification settings - Fork 0
/
133-heap_extract.c
140 lines (120 loc) · 2.46 KB
/
133-heap_extract.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
#include "binary_trees.h"
#include <stdlib.h>
/**
* tree_height - measures the height of a binary tree
* @tree: pointer to the root node of the tree to measure the height
*
* Return: Height or 0 if tree is NULL
*/
size_t tree_height(const heap_t *tree)
{
size_t height_l = 0;
size_t height_r = 0;
if (!tree)
return (0);
if (tree->left)
height_l = 1 + tree_height(tree->left);
if (tree->right)
height_r = 1 + tree_height(tree->right);
if (height_l > height_r)
return (height_l);
return (height_r);
}
/**
* tree_size_h - measures the sum of heights of a binary tree
* @tree: pointer to the root node of the tree to measure the height
*
* Return: Height or 0 if tree is NULL
*/
size_t tree_size_h(const binary_tree_t *tree)
{
size_t height_l = 0;
size_t height_r = 0;
if (!tree)
return (0);
if (tree->left)
height_l = 1 + tree_size_h(tree->left);
if (tree->right)
height_r = 1 + tree_size_h(tree->right);
return (height_l + height_r);
}
/**
* _preorder - goes through a binary tree using pre-order traversal
* @tree: pointer to the root node of the tree to traverse
* @node: will be last note in traverse
* @height: height of tree
*
* Return: No Return
*/
void _preorder(heap_t *tree, heap_t **node, size_t height)
{
if (!tree)
return;
if (!height)
*node = tree;
height--;
_preorder(tree->left, node, height);
_preorder(tree->right, node, height);
}
/**
* heapify - heapifies max binary heap
* @root: pointer to binary heap
*/
void heapify(heap_t *root)
{
int value;
heap_t *tmp1, *tmp2;
if (!root)
return;
tmp1 = root;
while (1)
{
if (!tmp1->left)
break;
if (!tmp1->right)
tmp2 = tmp1->left;
else
{
if (tmp1->left->n > tmp1->right->n)
tmp2 = tmp1->left;
else
tmp2 = tmp1->right;
}
if (tmp1->n > tmp2->n)
break;
value = tmp1->n;
tmp1->n = tmp2->n;
tmp2->n = value;
tmp1 = tmp2;
}
}
/**
* heap_extract - extracts the root node from a Max Binary Heap
* @root: pointer to the heap root
* Return: value of extracted node
**/
int heap_extract(heap_t **root)
{
int value;
heap_t *heap_r, *node;
if (!root || !*root)
return (0);
heap_r = *root;
value = heap_r->n;
if (!heap_r->left && !heap_r->right)
{
*root = NULL;
free(heap_r);
return (value);
}
_preorder(heap_r, &node, tree_height(heap_r));
heap_r->n = node->n;
if (node->parent->right)
node->parent->right = NULL;
else
node->parent->left = NULL;
free(node);
heapify(heap_r);
*root = heap_r;
return (value);
}