#include <stdlib.h>
#include <stdIo.h>
typedef int ElementType;
typedef struct HNode *Heap; /* 堆的类型定义 */
struct HNode {
    ElementType *Data; /* 存储元素的数组 */
    int Size;          /* 堆中当前元素个数 */
    int Capacity;      /* 堆的最大容量 */
};
typedef Heap MaxHeap; /* 最大堆 */
#define MAXDATA 1000000  /* 该值应根据具体情况定义为大于堆中所有可能元素的值 */
 

MaxHeap InitializeHeap( int MaxSize )
{   /* 创建容量为MaxSize的空的最大堆 */
 
    MaxHeap H = (MaxHeap)malloc(sizeof(struct HNode));
    /* 多一个元素存放"哨兵" */
    H->Data = (ElementType *)malloc((MaxSize+1)*sizeof(ElementType));  
    
    H->Size = 0;
    H->Capacity = MaxSize;
    H->Data[0] = MAXDATA;  /* 定义"哨兵"为大于堆中所有可能元素的值*/
 
    return H;
}

bool IsFull( MaxHeap H )
{
    return (H->Size == H->Capacity);
}
bool IsEmpty( MaxHeap H )
{
    return (H->Size == 0);
}

void Insert( MaxHeap H, ElementType X )
{   /* 将元素X插入最大堆H，其中H->Data[0]已经定义为哨兵 */
    int i;
    /* 首先判断，堆是否已满。已满则结束 */
    if ( IsFull(H) ) { 
        printf("最大堆已满");
        return;
    }
      
    /* 若堆未满，i指向堆末尾的下一个位置(空穴，当前size+1)，准备插入X */
    i = ++H->Size;  /* 类似插入排序，  */
    /* 若X 大于 其父节点值，则将父节点值下移至位置i， i位置(空穴）移到父节点位置[i/2] */
    for ( ; H->Data[i/2] < X; i /= 2 )
        H->Data[i] = H->Data[i/2]; /* 上滤X */
    
    H->Data[i] = X; /* 将X插入 */
    /* 若X是当前堆中最大元素，那么会在堆顶时（比哨兵小）终止上移 */
}

ElementType DeleteMax( MaxHeap H )
{   /* 从最大堆H中取出键值为最大的元素，并删除一个结点 */
    int Parent, Child;   /* 指针 */
    ElementType MaxItem, X;    
    if ( IsEmpty(H) ) {
        printf("最大堆已为空"); /* 若堆已空，则结束（没得删） */
        return ERROR;
    }
 
    MaxItem = H->Data[1]; /* 取出根结点存放的最大值 */
    /* 用最大堆中最后一个元素X，从根结点开始，向上过滤下层结点 */
    X = H->Data[H->Size--]; /* 相当于删掉末尾元素位置，故当前堆size要减1*/
    
    /* 迭代地将X和其更大的孩子节点值作比较，并调整位置（从根节点开始，给X找个位置） */
    /* Parent*2 <= H->Size判断是否有左儿子(有无孩子)，若无则超出堆空间，跳出循环，直接把X放Parent */
    for ( Parent = 1; Parent*2 <= H->Size; Parent = Child ) {
        /* 找到当前更大的孩子节点*/
        Child = Parent * 2;  /* 令Child为左儿子，经过外层for循环判断，Child只能 <= Parent */
        /* 若有右儿子((Child < H->Size))，则让让Child指向左右子结点的较大者 */
        if ( (Child != H->Size) && (H->Data[Child] < H->Data[Child+1]) )
            Child++; 
        /* 将末尾元素X和Child的值比较，若X >= Child值则结束（有序了）*/
        /* 若X < Child值 (Child更大)，则将Child值放在位置Parent，并将Parent位置移到Child位置 */
        if ( X >= H->Data[Child] ) 
            break;   /* 找到了合适位置 */
        else  /* Child元素上移，X移动到下一层（Parent = Child），继续和其孩子节点比较 */
            H->Data[Parent] = H->Data[Child];
    }
    H->Data[Parent] = X;
 
    return MaxItem;
} 

void PercolateDown( MaxHeap H, int p )
{   /* 下滤：将H中以H->Data[p]为根的子堆调整为最大堆 */
    int Parent, Child;
    ElementType X = H->Data[p]; /* 取出根结点存放的值 */
    for ( Parent=p; Parent*2<=H->Size; Parent=Child ) {
        Child = Parent * 2;
        if ( (Child!=H->Size) && (H->Data[Child]<H->Data[Child+1]) )
            Child++;  /* Child指向左右子结点的较大者 */
        if ( X >= H->Data[Child] )  break; /* 找到了合适位置 */
        else  /* 下滤X */
            H->Data[Parent] = H->Data[Child];
    }
    H->Data[Parent] = X;
}
 
void BuildHeap( MaxHeap H )
{   /* 调整H->Data[]中的元素，使满足最大堆的有序性  */
    /* 这里假设所有H->Size个元素已经存在H->Data[]中 */
 
    int i;
 
    /* 从最后一个结点的父节点开始，到根结点1 */
    for ( i = H->Size/2; i > 0; i-- )
        PercolateDown( H, i );
}

ElementType DeleteMax( MaxHeap H )
{   /* 从最大堆H中取出键值为最大的元素，并删除一个结点 */
    ElementType MaxItem = H->Data[1]; /* 取出根结点存放的最大值 */
  
    H->Data[1] = H->Data[H->Size--]   /* 取出根结点存放的最大值 */
  
    PercolateDown(H, 1);  /* 从根结点开始，向上过滤下层结点（末尾节点下滤） */
    return MaxItem;
} 

class Heap:
    def __init__(self, n):
        self.capacity = n
        self.size = 0
        self.arr = [None] * (self.capacity+1)
        self.arr[0] = 2e24
 
    def insert(self, num): 
        if self.size == self.capacity:
            print("Out of size")
        else:
            self.size += 1
            child = self.size  # 空穴位置
            # 上滤, 当左儿子在堆范围内
            while num > self.arr[child // 2]:
                parent = child // 2
                self.arr[child] = self.arr[parent]
                child = parent
            self.arr[child] = num
    def pop(self): 
        if self.size == 0:
            print("Empty")
        else:
            max_item = self.arr[1] # 取堆顶
            x = self.arr[self.size] # 取堆末尾元素
            self.size -= 1
            parent = 1
            # 下滤, 当左儿子在堆范围内
            while parent * 2  <= self.size:
                child = parent * 2 
                if child != self.size and self.arr[child+1] > self.arr[child]:
                    child += 1
                if self.arr[child] > x:
                    self.arr[parent] = self.arr[child] # 孩子节点值上移
                    parent = child
                else:
                    break
            self.arr[parent] = x
            return max_item

import queue
, random
class Heap():
    def __init__(self, k):
        if k > 0:
            self.q = queue.PriorityQueue(k)
    def queue(self):
        return self.q.queue
        
    def enque(self, key):
        # 当前堆大小小于其容量 
        if self.q._qsize() < self.q.maxsize:
            self.q.put(key)
        else:
            self.q.get() # 删除堆顶 
            self.q.put(key)
    def deque(self):
        if not self.q.empty():
            return self.q.get()
        else:
            print("Empty heap")
h1 = Heap(10)
for i in range(15):
    h1.enque(i)
print(h1.queue())  # 最小堆，k  可得到堆排序得到最大的k个 
l1 = [ random.randint(1, 100) for i in range(20)]
print(l1)
for i in l1:
    h1.enque(i)
    
print(h1.queue())
print("\nPriority Queue:")
print([h1.deque() for i in range(h1.q._qsize())])