// Tworzenie kopca w tablicy
// Data: 27.02.2013
// (C)2013 mgr Jerzy Wałaszek
//------------------------------

program create_heap;

// Zmienne globalne

var
  // łańcuchy do znaków ramek
  cr, cl, cp : string;
  // kopiec
  T : array [0..14] of integer;
  // liczba węzłów
  n : integer;

// Procedura wypisuje drzewo
//--------------------------
procedure print_bt(sp, sn : string;
                  v : integer);
var
  s : string;
  i : integer;
begin
  if v < n then
  begin
    s := sp;
    if sn = cr then
      s[length(s)-1] := ' ';
    print_bt(s+cp, cr, 2*v+2);

    s := Copy(sp, 1, length(sp)-2);
    for i := 1 to length(s) do
      write(char(ord(s[i])));
    for i := 1 to length(sn) do
      write(char(ord(sn[i])));
    writeln(T[v]);

    s := sp;
    if sn = cl then
      s[length(s)-1] := ' ';
    print_bt(s+cp, cl, 2*v+1);
  end;
end;

// procedura wstawia v do kopca
//-----------------------------
procedure heap_push(v : integer);
var
  i, j : integer;
begin
  i := n;
  inc(n);
  j := (i-1) div 2;

  while(i > 0) and (T[j] < v) do
  begin
    T[i] := T[j];
    i := j;
    j := (i-1) div 2;
  end;

  T[i] := v;
end;

// **********************
// *** PROGRAM GŁÓWNY ***
// **********************

var
  i, v : integer;
begin
  // ustawiamy łańcuchy znakowe, 
  // ponieważ nie wszystkie edytory
  // pozwalają wstawiać znaki konsoli
  // do tworzenia ramek.

  // cr = +--
  //      |

  // cl = |
  //      +--

  // cp = |
  //      |

  cr := #218#196;
  cl := #192#196;
  cp := #179#32;

  randomize;

  n := 0;

  for i := 1 to 15 do
  begin
    v := random(100);
    write(v, ' ');
    heap_push(v);
  end;

  writeln;
  writeln;

  print_bt('', '', 0);
end.

// Tworzenie kopca w tablicy
// Data: 27.02.2013
// (C)2013 mgr Jerzy Wałaszek
//------------------------------

#include <iostream>
#include <string>
#include <ctime>
#include <cstdlib>

using namespace std;

// Zmienne globalne

// łańcuchy do znaków ramek
string cr, cl, cp;
// tablica na kopiec
int T [15];
// liczba elementów w kopcu
int n = 0;

// Procedura wypisuje drzewo
//--------------------------
void print_bt(string sp, 
             string sn, 
             int v)
{
  string s;

  if(v < n)
  {
    s = sp;
    if(sn == cr)
      s[s.length()-2] = ' ';
    print_bt(s+cp, cr, 2*v+2);

    s = s.substr(0, sp.length()-2);
    cout << s << sn << T[v]
         << endl;

    s = sp;
    if(sn == cl)
        s[s.length()-2] = ' ';
    print_bt(s+cp, cl, 2*v+1);
  }
}

// procedura wstawia v do kopca
//-----------------------------
void heap_push(int v)
{
  int i, j;

  i = n++;
  j = (i-1)/2;

  while(i > 0 && T[j] < v)
  {
    T[i] = T[j];
    i = j;
    j = (i-1)/2;
  }

  T[i] = v;
}

// **********************
// *** PROGRAM GŁÓWNY ***
// **********************

int main()
{
  int i, v;

  srand(time(NULL));

  // ustawiamy łańcuchy znakowe, 
  // ponieważ nie wszystkie edytory
  // pozwalają wstawiać znaki konsoli
  // do tworzenia ramek.

  // cr = +--
  //      |

  // cl = |
  //      +--

  // cp = |
  //      |

  cr = cl = cp = "  ";
  cr[0] = 218; cr[1] = 196;
  cl[0] = 192; cl[1] = 196;
  cp[0] = 179;

  for(i = 0; i < 15; i++)
  {
    v = rand() % 100;
    cout << v << " ";
    heap_push(v);
  }

  cout << endl << endl;
  print_bt("", "", 0);

  return 0;
}

' Tworzenie kopca w tablicy
' Data: 27.02.2013
' (C)2013 mgr Jerzy Wałaszek
'------------------------------

Dim Shared As Integer T(0 To 14)
Dim Shared As Integer n = 0
Dim Shared As String * 2 crx, clx, cpx

' Procedura wypisuje drzewo
'--------------------------
Sub print_bt(sp As String, _
            sn As String, _
            v As Integer)
  Dim As String s

  If v < n Then
    s = sp
    If sn = crx Then _
      Mid(s, Len(s)-1, 1) = " "
    print_bt(s+cpx, crx, 2*v+2)

    s = Mid(s, 1, Len(sp)-2)
    Print Using "&&&";s;sn;T(v)

    s = sp
    If sn = clx Then _
      Mid(s, Len(s)-1, 1) = " "
    print_bt(s+cpx, clx, 2*v+1)
  End If
End Sub

' procedura wstawia v do kopca
'-----------------------------
Sub heap_push(v As Integer)

  Dim As Integer i, j

  i = n
  n += 1
  j = (i-1)\2

  While i > 0 AndAlso T(j) < v
    T(i) = T(j)
    i = j
    j = (i-1)\2
  Wend

  T(i) = v
End Sub

' **********************
' *** PROGRAM GŁÓWNY ***
' **********************

Dim As Integer i, v

Randomize

' ustawiamy łańcuchy znakowe, 
' ponieważ nie wszystkie edytory
' pozwalają wstawiać znaki konsoli
' do tworzenia ramek.

' crx = +--
'       |

' clx = |
'       +--

' cpx = |
'       |

crx = Chr(218)+Chr(196)
clx = Chr(192)+Chr(196)
cpx = Chr(179)+" "
 
For i = 1 To 15
  v = Int(Rnd()*100)
  print v;
  heap_push(v)
Next

Print
Print

print_bt("", "", 0)
End

// Usuwanie elementu z kopca
// Data: 5.03.2013
// (C)2013 mgr Jerzy Wałaszek
//---------------------------

program heapsort;

var
  // kopiec
  T : array [0..199] of integer;
  // liczba węzłów w kopcu
  n : integer;

// Procedura wstawia v do kopca
//-----------------------------
procedure heap_push(v : integer);
var
  i, j : integer;
begin
  i := n;
  inc(n);
  j := (i-1) div 2;
  while(i > 0) and (T[j] < v) do
  begin
    T[i] := T[j];
    i := j;
    j := (i-1) div 2;
  end;
  T[i] := v;
end;

// Procedura usuwa korzeń z kopca
//-------------------------------
procedure heap_pop;
var
  i, j, v : integer;
begin
  if n > 0 then
  begin
    dec(n);
    v := T[n];
    i := 0;
    j := 1;
    while j < n do
    begin
      if(j+1 < n) and (T[j+1] > T[j]) then
        inc(j);
      if v >= T[j] then break;
      T[i] := T[j];
      i := j;
      j := 2*j+1;
    end;
    T[i] := v;
  end;
end;

// **********************
// *** PROGRAM GŁÓWNY ***
// **********************

var
  i, v : integer;
begin
  randomize;
  n := 0;

  // Tworzymy kopiec
  for i := 1 to 200 do
  begin
    v := random(199)-99;
    write(v:4);
    heap_push(v);
  end;
  writeln;
  writeln;

  // Rozbieramy kopiec
  while n > 0 do
  begin
    write(T[0]:4);
    heap_pop;
  end;
  writeln;
  writeln;
end.

// Usuwanie elementu z kopca
// Data: 5.03.2013
// (C)2013 mgr Jerzy Wałaszek
//------------------------------

#include <iostream>
#include <iomanip>
#include <ctime>
#include <cstdlib>

using namespace std;

int T[200]; // kopiec
int n = 0; // liczba węzłów

// Procedura wstawia v do kopca
//-----------------------------
void heap_push(int v)
{
  int i, j;

  i = n++;
  j = (i-1) / 2;
  while(i > 0 && T[j] < v)
  {
    T[i] = T[j];
    i = j;
    j = (i-1)/2;
  }
  T[i] = v;
}

// Procedura usuwa korzeń z kopca
//------------------------------
void heap_pop()
{
  int i, j, v;

  if(n--)
  {
    v = T[n];
    i = 0;
    j = 1;
    while(j < n)
    {
      if(j+1 < n && T[j+1] > T[j])
        j++;
      if(v >= T[j]) break;
      T[i] = T[j];
      i = j;
      j = 2*j+1;
    }
    T[i] = v;
  }
}

// **********************
// *** PROGRAM GŁÓWNY ***
// **********************

int main()
{
  int i, v;

  srand(time(NULL));

  // Tworzymy kopiec
  for(i = 0; i < 200; i++)
  {
    v = (rand()%199)-99;
    cout << setw(4) << v;
    heap_push(v);
  }
  cout << endl << endl;

  // Rozbieramy kopiec
  while(n)
  {
    cout << setw(4) << T[0];
    heap_pop();
  }
  cout << endl << endl;

  return 0;
}

' Usuwanie elementu z kopca
' Data: 5.03.2013
' (C)2013 mgr Jerzy Wałaszek
'---------------------------

' kopiec
Dim Shared As integer T(0 To 199)
' liczba węzłów
Dim Shared As Integer n = 0

' Procedura wstawia v do kopca
'-----------------------------
Sub heap_push(ByVal v As Integer)
  Dim As Integer i, j

  i = n
  n += 1
  j = (i-1)\2
  While(i > 0) AndAlso (T(j) < v)
    T(i) = T(j)
    i = j
    j = (i-1)\2
  Wend
  T(i) = v
End Sub

' Procedura usuwa korzeń z kopca
'------------------------------
Sub heap_pop()
  Dim As Integer i, j, v

  If n > 0 Then
    n -= 1
    v = T(n)
    i = 0
    j = 1
    While j < n
      if(j+1 < n) AndAlso _
        (T(j+1) > T(j)) Then _
        j += 1
      If v >= T (j) Then _
        Exit While
      T(i) = T(j)
      i = j
      j = 2*j+1
    Wend
    T(i) = v
  End If
End Sub

' **********************
' *** PROGRAM GŁÓWNY ***
' **********************

Dim As Integer i, v

Randomize

' Tworzymy kopiec
For i = 1 To 200
  v = Int(Rnd()*199)-99
  Print Using "####";v;
  heap_push(v)
Next
Print
Print

' Rozbieramy kopiec
While n > 0
  Print Using "####";T(0);
  heap_pop()
Wend
Print
Print
End

// Kolejka priorytetowa z kopcem
// Data: 5.03.2013
// (C)2013 mgr Jerzy Wałaszek
//------------------------------

program heap_queue;

// Definicja typu obiektowego queue
//---------------------------------
  type
    Qel = record
      prio : integer;
      Data: integer;
    end;

    TQel = array of Qel;

  Queue = object
    private
      // kopiec dynamiczny
      T : TQel;
      // liczba elementów
      n : integer;

    public
      constructor init(max_n : integer);
      destructor  destroy;
      function    q_empty : boolean;
      function    q_front : integer;
      function    q_frontprio: integer;
      procedure   push(prio, v : integer);
      procedure   q_pop;
  end;

//----------------------
// Metody obiektu Queue
//----------------------

// Konstruktor-rezerwuje pamięć na kopiec
//---------------------------------------
constructor Queue.init(max_n : integer);
begin
  // tworzymy tablicę dynamiczną
  SetLength(T, max_n);
  n := 0; // kopiec jest pusty
end;

// Destruktor-usuwa tablicę z pamięci
//-----------------------------------
destructor Queue.destroy;
begin
  SetLength(T, 0);
end;

// Sprawdza, czy kolejka jest pusta
//---------------------------------
function Queue.q_empty : boolean;
begin
  q_empty := (n = 0);
end;

// Zwraca początek kolejki.
// Wartość specjalna to -MAXINT
//-----------------------------
function Queue.q_front : integer;
begin
  if n = 0 then q_front := -MAXINT
  else          q_front := T[0].data;
end;

// Zwraca priorytet pierwszego elementu
//-------------------------------------
function Queue.q_frontprio : integer;
begin
  if n = 0 then q_frontprio := -MAXINT
  else          q_frontprio := T[0].prio;
end;

// Zapisuje do kolejki wg priorytetu
//----------------------------------
procedure Queue.push(prio, v : integer);
var
  i, j : integer;
begin
  i := n;
  inc(n);
  j := (i-1) div 2;
  while(i > 0) and (T[j].prio < prio) do
  begin
    T[i] := T[j];
    i := j;
    j := (i-1) div 2;
  end;
  T[i].prio := prio;
  T[i].Data:= v;
end;

// Usuwa z kolejki
//----------------
procedure Queue.q_pop;
var
  i, j, v, p : integer;
begin
  if n > 0 then
  begin
    dec(n);
    p := T[n].prio;
    v := T[n].data;
    i := 0;
    j := 1;
    while j < n do
    begin
      if(j+1 < n) and
        (T[j+1].prio > T[j].prio) then
        inc(j);
      if p >= T[j].prio then break;
      T[i] := T[j];
      i := j;
      j := 2*j+1;
    end;
    T[i].prio := p;
    T[i].Data:= v;
  end;
end;

//---------------
// Program główny
//---------------

var
  // kolejka 10-cio elementowa
  Q : Queue;
  i, p, v : integer;

begin
  Randomize;
  Q.init(10);
  for i := 1 to 10 do
  begin
    v := random(100);
    p := random(10);
    writeln(v:2, ':', p);
    Q.push(p, v);
  end;

  writeln('----');

  while not Q.q_empty do
  begin
    writeln(Q.q_front:2, ':', Q.q_frontprio);
    Q.q_pop;
  end;

  Q.destroy;
end.

// Kolejka priorytetowa z kopcem
// Data: 5.03.2013
// (C)2013 mgr Jerzy Wałaszek
//------------------------------

#include <iostream>
#include <iomanip>
#include <ctime>
#include <cstdlib>

using namespace std;

const int MAXINT = -2147483647;

// Definicja typu obiektowego Queue
//----------------------------------

 struct Qel
 {
   int prio, data;
 };

class Queue
{
  private:
    // kopiec dynamiczny
    Qel * T;
    // liczba elementów
    int n;

  public:
    Queue(int max_n);
    ~Queue();
    bool empty();
    int  front();
    int  frontprio();
    void push(int prio, int v);
    void pop();
};

//----------------------
// Metody obiektu Queue
//----------------------

// Konstruktor-rezerwuje pamięć na kopiec
//---------------------------------------
Queue::Queue(int max_n)
{
  // tworzymy tablicę dynamiczną
  T = new Qel[max_n];
  n = 0; // kopiec jest pusty
}

// Destruktor-usuwa tablicę z pamięci
//-----------------------------------
Queue::~Queue()
{
  delete [] T;
}

// Sprawdza, czy kolejka jest pusta
//---------------------------------
bool Queue::empty()
{
  return !n;
}

// Zwraca początek kolejki.
// Wartość specjalna to MAXINT
//----------------------------
int Queue::front()
{
  return n ? T[0].Data: MAXINT;
}

// Zwraca priorytet pierwszego elementu
//-------------------------------------
int Queue::frontprio()
{
  return n ? T[0].prio : MAXINT;
}

// Zapisuje do kolejki wg priorytetu
//----------------------------------
void Queue::push(int prio, int v)
{
  int i, j;

  i = n++;
  j = (i-1)/2;
  while(i > 0 && T[j].prio < prio)
  {
    T[i] = T[j];
    i = j;
    j = (i-1)/2;
  }
  T[i].prio = prio;
  T[i].data = v;
}

// Usuwa z kolejki
//----------------
void Queue::pop()
{
  int i, j, v, p;

  if(n--)
  {
    p = T[n].prio;
    v = T[n].data;
    i = 0;
    j = 1;
    while(j < n)
    {
      if(j+1 < n &&
         T[j+1].prio > T[j].prio)
        j++;
      if(p >= T[j].prio) break;
      T[i] = T[j];
      i = j;
      j = 2*j+1;
    }
    T[i].prio = p;
    T[i].data = v;
  }
}

//---------------
// Program główny
//---------------

int main()
{
  // kolejka 10-cio elementowa
  Queue Q(10);
  int i, p, v;

  srand(time(NULL));

  for(i = 0; i < 10; i++)
  {
     v = rand()%100;
     p = rand()%10;
     cout << setw(2) << v << ":" << p
          << endl;
     Q.push(p, v);
  }

  cout << "----\n";

  while(!Q.empty())
  {
    cout << setw(2) << Q.front()
         << ":" << Q.frontprio()
         << endl;
    Q.pop();
  }
  return 0;
}

' Kolejka priorytetowa z kopcem
' Data: 5.03.2013
' (C)2020 mgr Jerzy Wałaszek
'------------------------------

Const MAXINT = 2147483647

' Definicja typu obiektowego Queue
'----------------------------------
Type Qel
  prio As Integer
  Data As Integer
End Type

Type Queue
  Private:
    T As Qel Ptr
    n As Integer

  Public:
    Declare Constructor(max_n As integer)
    Declare Destructor
    Declare Function q_empty As Integer
    Declare Function q_front As Integer
    Declare Function q_frontprio As Integer
    Declare Sub push(ByVal prio As Integer, _
                       ByVal v As Integer)
    Declare Sub q_pop
End Type

'---------------
' Program główny
'---------------

' kolejka 10-cio elementowa
Dim Q As Queue = 10
Dim As Integer i, p, v

Randomize

For i = 1 To 10
  v = Int(Rnd*100)
  p = Int(Rnd*10)
  Print Using "##:#";v;p
  Q.push(p, v)
Next

Print "----"

While Q.q_empty = 0
  Print Using "##:#";Q.q_front;Q.q_frontprio
  Q.q_pop
Wend
End

'----------------------
' Metody obiektu Queue
'----------------------

' Konstruktor-tworzy pustą listę
'---------------------------------
Constructor Queue(max_n As Integer)
  T = New Qel[max_n]
  n = 0
End Constructor

' Destruktor-usuwa listę z pamięci
'-----------------------------------
Destructor Queue
  Delete [] T
End Destructor

' Sprawdza, czy kolejka jest pusta
'---------------------------------
Function Queue.q_empty As Integer
  If n = 0 Then Return 1
  Return 0
End Function

' Zwraca początek kolejki.
' Wartość specjalna to -MAXINT
'-----------------------------
Function Queue.q_front As Integer
  If n = 0 then
    q_front = -MAXINT
  Else
    q_front = T[0].data
  End If
End Function

' Zwraca priorytet pierwszego elementu
'-------------------------------------
Function Queue.q_frontprio As Integer
  If n = 0 then
    q_frontprio = -MAXINT
  Else
    q_frontprio = T[0].prio
  End If
End Function

' Zapisuje do kolejki
'--------------------
Sub Queue.push(ByVal prio As Integer, _
                  ByVal v As Integer)
  Dim As Integer i, j

  i = n
  n += 1
  j = (i-1)\2
  While i > 0 AndAlso T[j].prio < prio
    T[i] = T[j]
    i = j
    j = (i-1)\2
  Wend
  T[i].prio = prio
  T[i].data = v
End Sub

' Usuwa z kolejki
'----------------
Sub Queue.q_pop
  Dim As Integer i, j, v, p

  If n > 0 Then
    n -= 1
    p = T[n].prio
    v = T[n].data
    i = 0
    j = 1
    While j < n
      if(j+1 < n) AndAlso _
        (T[j+1].prio > T[j].prio) Then _
        j += 1
      If p >= T[j].prio Then Exit While
      T[i] = T[j]
      i = j
      j = 2*j+1
    Wend
    T[i].prio = p
    T[i].data = v
  End If
End Sub