PROGRAM Time_Queue
      USE Random_Numbers
      USE Sorting_Ranking
      USE StopWatch
      IMPLICIT NONE
      
      INTEGER::n_elements
      REAL,DIMENSION(:),ALLOCATABLE::array
      INTEGER,DIMENSION(:),ALLOCATABLE::queue,permutation
      INTEGER::counter,element,queue_size
      TYPE(WATCHTYPE)::timer
      
      INTEGER::child_index,child,parent_index,parent,temp_node
      LOGICAL::heap_test
      
      CALL CREATE_WATCH(timer)
      
      WRITE(*,*)"Enter array size:"
      READ(*,*)n_elements
      ALLOCATE(array(n_elements),queue(n_elements),permutation(n_elements))
      CALL RandomUniform(array)
      
      CALL START_WATCH(timer)
      queue_size=0
      DO element=1,n_elements
      IF(array(element)<=1.00)THEN
      
      queue_size=queue_size+1
      queue(queue_size)=element
      
      child_index=queue_size
      MoveUp_EnQueue:DO
      IF(child_index<=1)EXIT MoveUp_EnQueue
      parent_index=child_index/2
      
      heap_test=(array(queue(parent_index))<=array(queue(child_index)))
      IF(heap_test)EXIT MoveUp_EnQueue
      
      temp_node=queue(parent_index)
      queue(parent_index)=queue(child_index)
      queue(child_index)=temp_node
      child_index=parent_index
      END DO MoveUp_EnQueue
      END IF
      END DO
      
      counter=0
      DO WHILE(queue_size>0)
      
      element=queue(1)
      queue_size=queue_size-1
      IF(queue_size>0)THEN
      queue(1)=queue(queue_size+1)
      
      parent_index=1
      MoveDown_DeQueue:DO
      IF(2*parent_index>queue_size)EXIT MoveDown_DeQueue
      child_index=2*parent_index
      IF(2*parent_index+1<=queue_size)THEN
      
      heap_test=(array(queue(2*parent_index+1))<=array(queue(2*parent_index)))
      IF(heap_test)child_index=2*parent_index+1
      END IF
      
      heap_test=(array(queue(parent_index))<=array(queue(child_index)))
      IF(heap_test)EXIT MoveDown_DeQueue
      
      temp_node=queue(parent_index)
      queue(parent_index)=queue(child_index)
      queue(child_index)=temp_node
      parent_index=child_index
      END DO MoveDown_DeQueue
      END IF
      counter=counter+1
      permutation(counter)=element
      END DO
      CALL STOP_WATCH(timer)
      CALL PRINT_WATCH(timer)
      
      CALL RESET_WATCH(timer)
      CALL START_WATCH(timer)
      CALL QuickRank(array=array,permutation=permutation,pivot_selection="U")
      CALL STOP_WATCH(timer)
      CALL PRINT_WATCH(timer)
      
      CALL RESET_WATCH(timer)
      CALL START_WATCH(timer)
      CALL HashRank(array=array,permutation=permutation,distribution="U")
      CALL STOP_WATCH(timer)
      CALL PRINT_WATCH(timer)
      
      END PROGRAM Time_Queue