require "./spec_helper"

describe Array do
  describe "#heapify" do
    it "preserves the elements in the array" do
      a = Array(Int32).new(20) { rand(10) }
      a.sort.should eq(a.clone.heapify!.sort)
    end

    it "creates an array with proper ordering" do
      a = Array(Int32).new(20) { rand(10) }
      a.heapify!
      a.is_heap?.should be_true
    end

    it "maintains heap property while popping" do
      a = Array(Int32).new(20) { rand(10) }
      a.heapify!
      20.times do |i|
        a.heap_pop
        a.is_heap?.should be_true
      end
    end

    it "maintains heap property while pushing" do
      a = [] of Int32
      20.times do 
        a.heap_push(rand 10)
        a.is_heap?.should be_true
      end
    end

    it "pops numbers in descending order" do
      a = Array(Int32).new(20) { rand(10) }
      a.heapify!
      last = Int32::MAX
      20.times do
        popped = a.heap_pop
        popped.should be <= last
        last = popped
      end
    end
  end
end