#include <iostream>
#include <vector>
#include <list>
using namespace std;

struct heap_elements;

struct list_segments {  //Структура отрезка - элемента списка отрезок
    int l;
    int r;
    int status;         // Но лучше просто считать это элементов класса и делать del по указателю
    int position; //Найдя по указателю отерзок поймём какой он в списке и вызовем del(pos)
    struct list_segments *next;
    struct list_segments *prev;
    heap_elements *to_heap; //Указатель на себя в куче (элемент структуры heap_elements)

};
struct heap_elements {
    int l;
    int r;
    int position;
    list_segments *to_list; //Указатель на себя в списке отрезков.
};


bool operator<(const heap_elements& a, const heap_elements& b)
{
    int len_a = a.r-a.l;
    int len_b = b.r-b.l;

    if ( (a.r-a.l < b.r-b.l) )
        return true;
    if ( (a.r-a.l == b.r-b.l) & (a.l > b.l))
        return true;

    return false;
}


class Heap
{
    static const int SIZE = 100; // максимальный размер кучи
    struct heap_elements* h; // указатель на массив кучи
    int HeapSize; // размер кучи
public:
    Heap(); // конструктор кучи
    void addelem(heap_elements); // добавление элемента кучи
    void outHeap(); // вывод элементов кучи в форме кучи
    void out(); // вывод элементов кучи в форме массива
    void siftup();
    void siftdown(int);
    void dalete(int);
};

Heap::Heap()
{
    h = new heap_elements[SIZE];
    HeapSize = 0;
}

void Heap::siftup()
{
    int i, parent;
    i = HeapSize - 1;
    parent = (i - 1) / 2;
    while (parent >= 0 && i > 0)
    {
        if (h[parent] < h[i])
        {
            heap_elements temp = h[i];
            h[i] = h[parent];
            h[parent] = temp;
            h[i].position = i;
            h[parent].position = parent;
        }
        i = parent;
        parent = (i - 1) / 2;
    }
}

void Heap::addelem(heap_elements elem)
{

    h[HeapSize] = elem;
    //h[HeapSize].r = elem.r;
    //h[HeapSize].to_list=elem.to_list;
    h[HeapSize].position = HeapSize;
    HeapSize++;
    siftup();
    /*
  parent = (i-1)/2;
  while(parent >= 0 && i > 0)  {
    if(h[i] > h[parent]) {
      int temp = h[i];
      h[i] = h[parent];
      h[parent] = temp;
    }
    i = parent;
    parent = (i-1)/2;
  }
  */
}

void Heap::siftdown(int position)
{
    int i, parent;
    int max_child;
    i = position;
    int child1 = 2 * i + 1;
    int child2 = 2 * i + 2;
    if (h[child2] < h[child1])
        max_child = child1;
    else
        max_child = child2;

    while (child1 < HeapSize)
    {
        if (child1 == HeapSize - 1)
        {
            max_child = child1;
        }
        else if (h[child2] < h[child1])
            max_child = child1;
        else
            max_child = child2;

        if (h[i] < h[max_child])
        {
            heap_elements temp = h[i];
            h[i] = h[max_child];
            h[max_child] = temp;
            h[i].position = i;
            h[max_child].position = max_child;
        }
        i = max_child;
        child1 = 2 * i + 1;
        child2 = 2 * i + 2;
    }
}

void Heap::dalete (int position)
{

    h[position] = h[HeapSize - 1];
    h[HeapSize - 1].l = 0;
    h[HeapSize - 1].r = 0;
    HeapSize--;
    siftdown(position);
}

void Heap::out(void)
{
    for (int i = 0; i < HeapSize; i++)
    {
        cout << h[i].l << " "<<h[i].r<<" ";
    }
    cout << endl;
}

int main()
{
    Heap heap;
    //int k;
    heap_elements vertex;
    vertex.l = 1;
    vertex.r = 7;
    vertex.to_list = NULL;
    heap.addelem(vertex);
    vertex.l = 0;
    vertex.r = 2;
    vertex.to_list = NULL;
    heap.addelem(vertex);
    vertex.l = 4;
    vertex.r = 6;
    vertex.to_list = NULL;
    heap.addelem(vertex);

    heap.out();
    heap.dalete(0);
    heap.out();
    return 0;
}