优先队列趣味示例 An interesting example of PriorityQueue

本项目提供C++实现优先队列的一个趣味示例。
This project provides an interesting example of PriorityQueue. <无>

#pragma once
#include<stdio.h>
#include<iostream>
#include<stdlib.h>
#include<vector>
#include<time.h>
#include<cmath>
#include "HeapSort.h"

using namespace std;

template <typename E>
class PriorityQueue
{
public:
	PriorityQueue(vector<E> events)
	{
		datalist = events;
		srand(time(NULL));

		//Random generate priviledge:
		for (int index = 0; index < datalist.size(); index++)
		{
			int val = (int)(rand() * 1.0 / RAND_MAX * (pow(datalist.size(), 3) - 1) + 1);
			Event newEvent;
			newEvent.priority = val;
			newEvent.data = datalist.at(index);
			eventlist.push_back(newEvent);
		}//end loop

		int * priorityList = new int[datalist.size()];
		printf("Priority: ");
		for (int index = 0; index < datalist.size(); index++)
		{
			priorityList[index] = (eventlist.at(index).priority);
			printf("%d ", priorityList[index]);
		}
		printf("\nEvents: \n");
		for (int index = 0; index < eventlist.size(); index++)
		{
			cout << eventlist.at(index).data << endl;
		}
		printf("\n\n");

		heapSort(priorityList, datalist.size());

		for (int index = 0; index < eventlist.size(); index++)
		{
			if (eventlist.at(index).priority != priorityList[index])
			{
				Event temp = eventlist.at(index);
				for (int j = index; j < eventlist.size(); j++)
				{
					if (eventlist.at(j).priority == priorityList[index])
					{
						eventlist.at(index) = eventlist.at(j);
						eventlist.at(j) = temp;
						break;
					}
				}//end loop
			}//end if
		}//end loop

		printf("Priority: ");
		for (int index = 0; index < datalist.size(); index++)
			printf("%d ", eventlist.at(index).priority);
		printf("\nEvents: \n");
		for (int index = 0; index < eventlist.size(); index++)
		{
			datalist.at(index) = eventlist.at(index).data;
			cout << eventlist.at(index).data << endl;
		}
		printf("\n");

	}//end constructor

	vector<E> getSortedEventList()
	{
		return datalist;
	}

private:
	struct Event
	{
		int priority;
		E data;
	}newEvent;
	vector<Event> eventlist;
	vector<E> datalist;
};//end class.

#include<stdio.h>
#include<stdlib.h>
#include<vector>
#include "PriorityQueue.h"

using namespace std;

int main()
{
	vector<char *> events = { 
		"Go to lunch",
		"Submit homework",
		"Meet with Girlfriends",
		"Have a break",
		"Play games" };
	PriorityQueue<char *> createEvents(events);
	events = createEvents.getSortedEventList();
	printf("Sorted events: \n");
	for (int index = 0; index < events.size(); index++)
		cout << events.at(index) << endl;
	printf("\n");
	system("Pause");
	return 0;
}

#include<iostream>
#include "Heap.h"

using namespace std;

template<typename E>
void heapSort(E data[], int num)
{
	E maxVal;
	Heap<E> heap(data, num, num, 1);
	for (int index = 0; index < num; index++)
		maxVal = heap.removefirst();
}//end function

#pragma once

#include<stdio.h>
#include<stdlib.h>

using namespace std;

template <typename E>
class Heap
{
public:
	Heap(E* h, int num, int max, int o)
	{
		heap = h;
		n = num;
		maxsize = max;
		order = o;
		buildHeap();
	}//end constructor

	void printHeap()
	{
		printf("Maxium capability of the heap: %d\n", maxsize);
		for (int index = 0; index < size(); index++)
			printf("Element %d: %d\n", index, heap[index]);
	}//end function

	int size() const
	{
		return n;
	};
	
	//True if pos is a leaf
	bool isIndexLeaf(int pos) const
	{
		return (pos >= n/2) && (pos < n);
	}//end function

	int leftchildIndex(int pos) const
	{
		return 2 * pos + 1;
	}//return postion of left child

	int rightchildIndex(int pos) const
	{
		return 2 * pos + 2;
	}//end function

	int parentIndex(int pos) const
	{
		return (pos - 1) / 2;
	}//end function

	void buildHeap()
	{
		for (int i = n / 2 - 1; i >= 0; i--)
			shiftdown(i);
	}//end funcion

	void insertEle(E it)
	{
		//Assert(n < maxsize, "Heap is full!\n");
		int currIndex = n++;
		heap[currIndex] = it;
		//Now shift up until the current parent > current
		while ((currIndex != 0) && (compare(heap[currIndex], heap[parentIndex(currIndex)]) == order))
		{
			swap(currIndex, parentIndex(currIndex));
			currIndex = parentIndex(currIndex);
		}//end loop
	}//end function

	E removefirst()
	{
		//Assert(n > 0, "Heap is empty");
		swap(0, --n);
		if (n != 0) shiftdown(0);
		return heap[n];
	}//end function: Remove the root

	E removeAt(int pos)
	{
		//Assert((pos >= 0) && (pos < n), "Bad position!");
		if (pos == (n - 1)) n--;
		else
		{
			swap(pos, --n);
			while ((pos != 0) && (compare(heap[pos], heap[parentIndex(pos)]) == order))
			{
				swap(pos, parentIndex(pos));
				pos = parentIndex(pos);
			}//end loop: Rearrange the heap.
			if (n != 0) shiftdown(pos);
		}//end if-else
		return heap[n];
	}//end function: remove

private:
	E* heap; //Ptr to the heap array
	int maxsize; //Maxium size of the heap
	int n; //Num of elements now in the heap
	int order;

	int compare(E e1, E e2)
	{
		if (e1 > e2)
			return 1;
		else
			return -1;
	}//end int

	//Helper function to put elements in its correct place:
	void shiftdown(int pos)
	{
		while (!isIndexLeaf(pos)) //Stop if pos is a leaf
		{
			int j = leftchildIndex(pos);
			int rc = rightchildIndex(pos);

			//By default, right node is larger than left node.
			if ((rc < n) && (compare(heap[rc], heap[j]) == order))
				j = rc;
			if (compare(heap[pos], heap[j]) == order)
				return;
			swap(pos, j);
			pos = j;
		}//end loop
	}//end function

	void swap(int des, int tar)
	{
		E temp = heap[des];
		heap[des] = heap[tar];
		heap[tar] = temp;
	}//end swap: Swap the elements.
};//end class: Heap implementation