上机5_树

题目

编写一个函数，在最大堆中查找任意元素，并分析其时间复杂度。
要求：
1、 定义最大堆的型HEAP及其基本操作。
2、 定义函数int Find(HEAP H, Elementtype e)，查找e是否为堆的元素，如果是，返回该元素在堆中的位置，如果不是，返回0。（提示：利用最大堆的元素特点进行查找，可降低复杂度）
在主函数中首先构建一个二叉树，然后验证所构造的函数。

代码一

#include<iostream>
#define MaxSize 200
using namespace std;
struct HEAP {
   
	int elements[MaxSize];
	int n;
};
void MaxHeap(HEAP& heap) {
   
	heap.n = 0;
}
bool HeapEmpty(HEAP& heap) {
   
	return !heap.n;
}
bool HeapFull(HEAP& heap) {
   
	return heap.n == MaxSize - 1;
}
void Insert(HEAP& heap, int item) {
   
	int i = 0;
	if (!HeapFull(heap)) {
   
		heap.n++;
		i = heap.n;
		while ((i != 1) && (item > heap.elements[i / 2])) {
   
			heap.elements[i] = heap.elements[i / 2];
			i /= 2;
		}
		heap.elements[i] = item;
	}
}
int DeleteMax(HEAP& heap) {
   
	int parent = 1, child = 2;
	int item, tmp;
	if (!HeapEmpty(heap)) {
   
		item = heap.elements[1];
		tmp = heap.elements[heap.n--];
		while (child <= heap.n) {
   
			if ((child < heap.n) && (heap.elements[child] < heap.elements[child + 1]))
				child++;
			if (tmp >= heap.elements[child])break;
			heap.elements[parent] = heap.elements[child];
			parent = child;
			child *= 2;
		}
		heap.elements[parent] = tmp;
		return item;
	}
	return NULL;
}
void print(HEAP& heap) {
   
	for (int i = 1; i <= heap.n; i++) {
   
		cout << heap.elements[i] << endl;
	}
}
int main() {
   
	HEAP heap = HEAP();
	MaxHeap(heap);
	Insert(heap, 93);
	Insert(heap, 87);
	Insert(heap, 79);
	Insert(heap, 67);
	Insert(heap, 54);
	Insert(heap, 74);
	Insert(heap, 43);
	print(heap);
	cout << "插入76" << endl;
	Insert(heap, 76);
	print(heap);
	cout << "删除最大值" << endl;
	DeleteMax(heap);
	print(heap);
}

代码二

#define kMaxSize 200

#include <iostream>
using namespace std;

typedef int elementtype;
typedef struct
{
   
    elementtype elements[kMaxSize];
    int n;
}HEAP;

void MaxHeap(HEAP& heap)
{
   
    heap.n = 0;
    for (int i = 1; i < kMaxSize; ++i)
    {
   
        heap.elements[i] = INT_MIN;
    }
}

bool HeapFull(HEAP heap)
{
   
    return (heap.n == kMaxSize - 1);
}

bool HeapEmpty(HEAP heap)
{
   
    return !heap.n;
}

void Insert(HEAP& heap, elementtype element)
{
   
    if (!HeapFull(heap))
    {
   
        int i = ++heap.n;
        while (i != 1 && (element > heap.elements[i / 2]))
        {
   
            heap.elements[i] = heap.elements[i / 2];
            i /= 2;
        }
        heap.elements[i] = element;
    }
}

elementtype DeleteMax(HEAP& heap)
{
   
    if (!HeapEmpty(heap))
    {
   
        int parent = 1, child = 2;
        elementtype element = heap.elements[1], tmp = heap.elements[heap.n--];
        while (child <= heap.n)
        {
   
            if ((child < heap.n) && (heap.elements[child] < heap.elements[child + 1]))
                ++child; //让child指向两子女中的大者位置
           //根大则不必调整，函数结束
            if (tmp >= heap.elements[child])
                break;        //否则子女中的大者上移
            heap.elements[parent] = heap.elements[child];
            parent = child; //将根下降到子女位置并继续向下整理！
            child *= 2;
        }
        heap.elements[parent] = tmp;
        return element;
    }
    return NULL;
}

int Find(HEAP heap, elementtype element)
{
   
    for (int i = 0; i < heap.n; ++i)
    {
   
        if (heap.elements[i + 1] == element)
        {
   
            return i + 1;
        }
    }
    return 0;
    //int i = 1; // 仅仅适用于 Insert 生成的最大堆，不具有普适性
    //while (i < heap.n)
    //{
   
    // if (heap.elements[i] == element)
    // {
   
    // return i;
    // }
    // else
    // {
   
    // if (heap.elements[2 * i] == element)
    // {
   
    // return 2 * i;
    // }
    // if (heap.elements[2 * i] < element)
    // {
   
    // i = 2 * i + 1;
    // }
    // else
    // {
   
    // ++i;
    // }
    // }
    //}
    //return 0;
}

int main()
{
   
    HEAP heap{
   };
    MaxHeap(heap);
    elementtype a[] = {
    99,88,5,77,66,1 };
    for (elementtype i : a)
    {
   
        Insert(heap, i);
    }
    //DeleteMax(heap);
    for (elementtype i : a)
    {
   
        cout << Find(heap, i) << endl;
    }
}