请用C++编写一段维护堆的程序
时间: 2023-05-28 21:04:46 浏览: 39
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100
void swap(int *x, int *y)
{
int temp = *x;
*x = *y;
*y = temp;
}
void max_heapify(int arr[], int size, int i)
{
int largest = i;
int left_child = 2 * i + 1;
int right_child = 2 * i + 2;
if (left_child < size && arr[left_child] > arr[largest])
largest = left_child;
if (right_child < size && arr[right_child] > arr[largest])
largest = right_child;
if (largest != i)
{
swap(&arr[i], &arr[largest]);
max_heapify(arr, size, largest);
}
}
void build_max_heap(int arr[], int size)
{
int i;
for (i = size / 2 - 1; i >= 0; i--)
max_heapify(arr, size, i);
}
void insert(int arr[], int *size, int element)
{
if (*size == MAX_SIZE)
{
printf("Heap full\n");
return;
}
arr[*size] = element;
(*size)++;
int i = *size - 1;
while (i != 0 && arr[(i - 1) / 2] < arr[i])
{
swap(&arr[i], &arr[(i - 1) / 2]);
i = (i - 1) / 2;
}
}
void delete(int arr[], int *size, int element)
{
int i;
for (i = 0; i < *size; i++)
{
if (arr[i] == element)
break;
}
if (i == *size)
{
printf("%d not found in heap\n", element);
return;
}
arr[i] = arr[*size - 1];
(*size)--;
max_heapify(arr, *size, i);
}
void print_heap(int arr[], int size)
{
int i;
for (i = 0; i < size; i++)
printf("%d ", arr[i]);
printf("\n");
}
int main()
{
int arr[MAX_SIZE] = { 10, 20, 15 };
int size = 3;
build_max_heap(arr, size);
printf("Heap before insertion: ");
print_heap(arr, size);
insert(arr, &size, 50);
printf("Heap after insertion of 50: ");
print_heap(arr, size);
delete(arr, &size, 20);
printf("Heap after deletion of 20: ");
print_heap(arr, size);
return 0;
}