simple ruby heap

rb_heap.rb

class Heap
  def initialize &block
    @data = []
    @less = block
  end

  def push i
    @data.push i
    len = @data.length
    upward(len-1)
  end

  def pop
    l = @data.length
    @data[0], @data[l-1] = @data[l-1], @data[0]
    r = @data.pop
    downward(0) if l >= 2
    r
  end

  def length
    @data.length
  end

  def top
    @data[0]
  end

  def upward n
    p = (n + 1) / 2 - 1
    if p >= 0 && @less.call(@data[n], @data[p])
        @data[n], @data[p] = @data[p], @data[n]
        upward(p)
    end
  end

  def downward n
    len = @data.length
    l = (n + 1) * 2 - 1
    r = (n + 1) * 2

    if l < len && @less.call(@data[l], @data[n])
        smaller = l
    else
        smaller = n
    end

    if r < len && @less.call(@data[r], @data[smaller])
        smaller = r
    end

    if smaller != n
        @data[n], @data[smaller] = @data[smaller], @data[n]
        downward(smaller)
    end
  end
end

h = Heap.new do |a, b|
  a < b
end

[2779, 4467, 6782, 3611, 3890, 7852, 7813, 4039, 8474, 6385, 4235, 2592, 3392, 784, 646, 6264, 7078, 1673, 3537, 265, 6780, 673, 5230, 2243, 7261, 511, 8362, 4982, 7046, 8431, 4500, 4207, 1519, 2084, 1347, 8838, 3115, 703, 9141, 2388, 9338, 2760, 5084, 7867, 4235, 2482, 2237, 5424, 8370, 3989, 3438, 8058, 8452, 7746, 3662, 4537, 9876, 2754, 7270, 1863, 283, 2033, 1672, 5396, 2796, 1051, 8935, 3434, 5035, 9068, 3803, 251, 4176, 3671, 8293, 9589, 457, 6819, 279, 41, 7616, 8490, 8235, 3336, 6690, 8328, 1116, 9407, 3373, 7641, 5945, 4818, 8310, 228, 5979, 2811, 2407, 6002, 3849, 4702, 1107, 2923, 2296, 8266, 4244, 5921, 6782, 1976, 7340, 8405, 7554, 876, 1348, 7322, 2863, 4901, 8150, 4101, 1087, 5580, 1997, 8500, 1517, 7568, 5004, 1967, 3222, 4751, 865, 7051, 240, 4422, 4327, 8063, 6597, 4408, 3864, 9091, 7932, 7671, 1980, 5892, 975, 3393, 4067, 4507, 8591, 5061, 255, 690, 8617, 4151, 7919, 9743, 4532, 5753, 7814, 599, 1654, 9005, 8911, 2810, 4450, 4189, 7998, 5393, 9824, 7452, 1758, 6789, 642, 9317, 7842, 1429, 1160, 7989, 2971, 4791, 323, 9185, 1225, 7033, 2913, 8815, 315, 8883, 2659, 4867, 2303, 2430, 1980, 5113, 2486, 4782, 6562, 3924, 4210, 2872, 2664, 9242, 946, 2505, 5860, 5661, 5172, 310, 8873, 5379, 8130, 8957, 6292, 1902, 2895, 6710, 232, 6730, 9125, 8432, 3366, 583, 7482, 7162, 7457, 4314, 2741, 5238, 9375, 5482, 9266, 494, 9008, 9781, 3794, 7448, 4519, 1495, 813, 9264, 3142, 6996, 6743, 8886, 309, 294, 4571, 368, 9780, 883, 3845, 8504, 9435, 9892, 3130, 3264, 3625, 7484, 5079, 6068, 5272, 5626, 3963, 8970, 6526, 6856, 8915, 6067, 5691, 2273, 621, 2640, 4346, 5042, 6721, 5211, 5226, 8417, 1958, 3193, 6566, 4521, 7236, 2050, 3269, 3599, 8219, 4243, 121, 2621, 6131, 7196, 1628, 4315, 4077, 7761, 5562, 884, 4874, 4718, 8587, 6038, 3406, 4496, 5487, 5828, 4816, 9129, 9638, 498, 1771, 1755, 2459, 9040, 5375, 6346, 9064, 5128, 3065, 4527, 3880, 4244, 4167, 9877, 1271, 3537, 890, 4187, 9623, 502, 8341, 1193, 2557, 1726, 5449, 782, 6763, 13, 1522, 742, 1502, 607, 6872, 7150, 2704, 8305, 3516, 5310, 5495, 8813, 7480, 5102, 739, 3825, 2791, 8962, 1036, 6155, 2605, 380, 1949, 6410, 2857, 9806, 3705, 2480, 9843, 5594, 914, 1839, 8102, 4675, 3858, 6650, 9651, 9902, 2165, 3967, 1166, 6665, 2310, 423, 5680, 8889, 5376, 4733, 409, 1165, 4227, 2448, 9775, 9537, 8100, 6401, 1274, 2419, 8794, 1264, 5027, 8634, 3125, 4800, 4721, 8809, 2724, 3799, 3240, 3456, 5041, 2505, 7617, 793, 2408, 1361, 4169, 8470, 6168, 8826, 746, 6605, 2399, 2948, 9022, 7021, 6357, 6528, 375, 6042, 4271, 6180, 799, 5958, 9274, 1204, 9961, 6667, 5874, 4626, 6684, 3138, 9255, 2206, 9362, 3797, 5436, 3598, 6963, 8462, 4117, 8438, 7256, 7571, 2395, 8022, 8833, 4266, 8171, 4083, 4349, 7737, 2979, 6358, 3605, 9498, 5364, 6042, 332, 678, 4092, 9532, 5132, 1707, 5367, 1044, 2683, 6363, 2623, 126, 8364, 2608, 9633, 8266, 4950, 7952, 8832, 6414, 1675, 2300, 1333, 5256, 8359, 4676, 8462, 9260, 5350, 6695, 2244, 8504, 2049, 215, 4120, 449, 6580, 3106, 5706, 4571, 4678, 7643, 508, 6517, 6315, 4214, 118, 6167, 1657, 6590, 7165, 8897, 2929, 5519, 9900, 5352, 748, 6287, 9342, 9687, 7433, 1690, 9508, 4401, 3577, 2923, 4592, 9464, 7411, 8732, 9428, 4172, 4592, 137, 2728, 3704, 4293, 6925, 8201, 5709, 7744, 4874, 7191, 3876, 101, 3158, 7236, 2698, 7919, 4988, 8349, 421, 6590, 8928, 6970, 2385, 4593, 7783, 5064, 3336, 666, 7715, 8598, 2233, 2410, 5840, 5256, 8288, 5086, 8847, 4726, 8815, 7942, 7532, 9365, 5724, 1939, 2280, 5652, 5767, 6472, 5217, 153, 6298, 2026, 8245, 8508, 4170, 2014, 2373, 3871, 1924, 6767, 2046, 1627, 1296, 1622, 3836, 9296, 7917, 5373, 4725, 4025, 9547, 1964, 187, 8648, 4944, 4842, 9409, 7425, 9716, 9782, 7844, 6357, 7636, 6643, 2823, 707, 8967, 4193, 2163, 9004, 7754, 9357, 147, 8844, 8656, 7371, 4859, 2454, 2379, 3790, 4787, 3897, 5960, 7402, 7234, 1487, 1048, 7525, 5186, 476, 9370, 1808, 5780, 3440, 8674, 8500, 7894, 2948, 5460, 307, 9007, 3391, 2799, 4210, 8067, 1739, 1682, 1290, 2133, 920, 1250, 3218, 6759, 3928, 659, 667, 9290, 4172, 3356, 7704, 2904, 4206, 8774, 7275, 6551, 2300, 9441, 4239, 8411, 3614, 2963, 3918, 9049, 4251, 739, 2108, 6055, 2348, 2239, 4486, 9546, 8381, 7078, 8529, 8247, 5052, 2901, 3258, 1915, 8445, 3639, 4575, 5717, 8002, 3778, 5324, 3265, 9131, 2365, 278, 7192, 5164, 4617, 7724, 9637, 3458, 1734, 1277, 6838, 9890, 1347, 8928, 9303, 752, 2351, 4584, 6102, 7255, 1484, 1899, 1850, 6586, 1136, 6651, 993, 1995, 9505, 4123, 8187, 6202, 7017, 11, 5405, 6574, 8176, 5704, 7000, 7463, 2763, 8188, 7259, 8797, 4947, 530, 6626, 7339, 1166, 2597, 6375, 5612, 9620, 3540, 2903, 1015, 3583, 1119, 9012, 607, 9339, 2425, 3855, 680, 9194, 6601, 4908, 5165, 1265, 2860, 4505, 6826, 5533, 303, 9070, 7577, 3652, 9311, 4328, 4878, 4889, 2204, 4566, 748, 3114, 1688, 3067, 6856, 4600, 1897, 5866, 7861, 1937, 9649, 14, 1960, 8356, 4798, 6571, 1389, 9618, 1969, 3135, 1149, 5939, 2350, 2413, 4852, 9046, 8075, 5461, 8474, 8749, 4504, 5375, 6035, 3056, 1852, 4923, 8377, 1454, 9221, 2007, 5982, 4621, 7300, 9220, 2549, 3331, 8761, 2873, 1072, 6796, 1962, 495, 6335, 5148, 3709, 721, 5871, 4592, 1190, 8323, 896, 8198, 1628, 2265, 9465, 6488, 7736, 9137, 9005, 7771, 5676, 4708, 4783, 5187, 2914, 2573, 2004, 9539, 2725, 2337, 9912, 7485, 2198, 3139, 4067, 1712, 4370, 8117, 6206, 6063, 9132, 6767, 4608, 9208, 9828, 4853, 8519, 8873, 16, 5328, 4245, 6640, 1722, 5853, 1158, 1973, 1498, 1596, 1891, 1015, 5067, 9707, 7525, 2491, 1582, 8839, 5814, 5152, 3278, 3233, 2479, 5187, 4607, 7097, 4931, 5216, 8375, 4454, 9449, 7864, 8913, 1981, 270, 5644, 6647, 9060, 8996, 4863, 1935, 8668, 405, 5660, 4448, 3103, 1911, 1170, 2680, 1952, 9408, 1418, 313, 4831, 2062, 3707, 6950, 4742, 5759, 1963, 8997, 4094, 73, 1500, 2580, 7864, 3937, 9921, 4818, 4527, 9464, 3355, 1691, 2121, 3539, 7082, 7968, 4188, 5618, 9126, 5918, 1846, 2906, 1786, 8288, 3390, 6507, 9021, 6844, 9732, 2123, 5760, 1693, 6446, 9105, 6512, 1469, 4813, 6410, 7994, 7093, 7349, 6619, 2718].each do |n|
    h.push n
end

while h.length > 0
    puts h.pop
end