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