최소힙정렬

class minheap:

    def __init__(self):
        self.lst = [None]
    def __init__(self,a): #리스트를 삽입
        self.lst=[None]+a[:]  #idx 0은 안쓸거라서 None포함
        for i in range(len(self.lst)//2,0,-1):#자식이 하나라도 있는 마지막 부모의 index가 len/2
            self.heapify(i)

    def heapify(self,i):
        left = self.leftchild(i)
        right = self.rightchild(i)
        small = i
        if left <=len(self.lst)-1 and self.lst[left]<self.lst[small]:
            small = left

        #right와 현재small값을 비교
        #left가 small이 되었다면 left와 right를 비교하므로 left와 right중 더작은 값을 small로 설정가능
        if right <=len(self.lst)-1 and self.lst[right]<self.lst[small]:
            small = right

        if small != i: #small이 자신(i) 아니라면
            self.swap(i,small)
            self.heapify(small)

    def leftchild(self,idx):
        return idx*2
    def rightchild(self,idx):
        return idx*2+1
    def parent(self,idx):
        return idx/2
    def insert(self,n):
        self.lst.append(n)
        i = len(self.lst)-1
        while i>1: #idx가 root가 될때까지
            parent = self.parent(i)
            if self.lst[i]<self.queue[parent]:
                self.swap(i,parent)
                i = parent
            else:
                break
    def delete(self):
        self.swap(1,len(self.lst)-1)
        print(self.lst.pop(len(self.lst)-1))
        self.heapify(1)

    def swap (self,a,b):
        self.lst[a],self.lst[b]=self.lst[b],self.lst[a]


    def __del__(self):
        for i in range(len(l)):
            self.delete()





l =[9,1,22,4,0,-1,1,22,100,10]
l1=[7,12,5,2,76,12,4,63,8,54]
h =minheap(l)
print(h.lst)

#include <algorithm>
#include <stdio.h>
#include <vector>
using namespace std;
vector<int> l,m;

void minheap(int x, int size)
{
	int left, right, p;
	while (x < size)
	{
		left = x * 2 + 1;
		right = x * 2 + 2;

		if (left >= size && right >= size)
			break;

		p = x;
		if (left < size && l[p] < l[left])
			p = left;
		if (right < size && l[p] < l[right])
			p = right;
		if (p == x)
			break;


		//swap
		int tmp = l[x];
		l[x] = l[p];
		l[p] = tmp;
		x = p;
	}
}


int main() {
	int n;
	scanf_s("%d", &n);
	l.resize(n);
	m.resize(n);


	for (int i =0 ; i < n; i++)
		scanf_s("%d", &l[i]);

	for (int i = n - 1 / 2; i >= 0; --i)
		minheap(i, n);

	for (int i = n - 1; i >= 0; --i)
	{
		m[i] = l[0];
		l[0] = l[i];
		minheap(0, i);
	}

	for (int a=0; a<m.size();a++)
		printf("%d\n", m[a]);


	return 0;
}