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

program create_heap;

// Zmienne globalne

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

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

    s := Copy (sp, 1, length (sp)-2);
    writeln(s, sn, T [v]);

    s := sp;
    if sn = cl then s [length (s) - 1] := ' ';
    printBT (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;

  printBT ('', '', 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

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

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

  if(v < n)
  {
    s = sp;
    if(sn == cr) s [s.length() - 2] = ' ';
    printBT (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] = ' ';
    printBT (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;

  printBT ("", "", 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 cr, cl, cp

' Procedura wypisuje drzewo
'--------------------------
Sub printBT (sp As String, sn As String, v As Integer)

  Dim As String s

  If v < n Then
    s = sp
    If sn = cr Then Mid (s, Len (s) - 1, 1) = " "
    printBT (s + cp, cr, 2 * v + 2)

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

    s = sp
    If sn = cl Then Mid (s, Len (s) - 1, 1) = " "
    printBT (s + cp, cl, 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.
' cr = +--
'      |

' cl = |
'      +--

' cp = |
'      |

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

Print
Print

printBT ("", "", 0)

End

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

program heapsort;

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

// 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
'------------------------------

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

' 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
    qelement = record
      prio : integer;
      data : integer;
    end;

    Tqelement = array of qelement;

  queue = object
    private

      T : Tqelement;  // kopiec dynamiczny
      n : integer;    // liczba elementów

    public
      constructor init (max_n : integer);
      destructor  destroy;
      function    empty : boolean;
      function    front : integer;
      function    frontprio: integer;
      procedure   push (prio, v : integer);
      procedure   pop;
  end;

//---------------------
// Metody obiektu queue
//---------------------

// Konstruktor - rezerwuje pamięć na kopiec
//-----------------------------------------
constructor queue.init (max_n : integer);
begin
  SetLength (T, max_n);  // tworzymy tablicę dynamiczną
  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.empty : boolean;
begin
  empty := (n = 0);
end;

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

// Zwraca priorytet pierwszego elementu
//-------------------------------------
function queue.frontprio : integer;
begin
  if n = 0 then frontprio := -MAXINT
  else          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.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
  Q : queue;   // kolejka 10-cio elementowa
  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.empty do
  begin
    writeln(Q.front:2, ':', Q.frontprio);
    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 qelement
 {
   int prio, data;
 };

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

  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)
{
  T = new qelement [max_n]; // tworzymy tablicę dynamiczną
  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()
{
  queue Q (10);   // kolejka 10-cio elementowa
  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();
  }
}

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

Const MAXINT = 2147483647

' Definicja typu obiektowego queue
'---------------------------------
Type qelement
  prio As Integer
  Data As Integer
End Type

Type queue
  Private:
    T As qelement Ptr
    n As Integer

  Public:
    Declare Constructor (max_n As integer)
    Declare Destructor()
    Declare Function empty() As Integer
    Declare Function front As Integer
    Declare Function frontprio As Integer
    Declare Sub push (ByVal prio As Integer, ByVal v As Integer)
    Declare Sub pop()
End Type

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

Dim Q As queue = 10  ' kolejka 10-cio elementowa
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.empty() = 0
  Print Using "##:#";Q.front();Q.frontprio()
  Q.pop()
Wend

End

'---------------------
' Metody obiektu queue
'---------------------

' Konstruktor - tworzy pustą listę
'---------------------------------
Constructor queue (max_n As Integer)
  T = New qelement [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.empty() As Integer
  If n = 0 Then Return 1
  Return 0
End Function

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

' Zwraca priorytet pierwszego elementu
'-------------------------------------
Function queue.frontprio() As Integer
  If n = 0 then
    frontprio = -MAXINT
  Else
    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.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